The Bowyer-Watson algorithm constructs a Delaunay triangulation of a set of points incrementally, inserting one point at a time, removing every triangle whose circumcircle contains the new point to leave a cavity, and retriangulating that cavity by connecting the new point to the cavity's boundary edges. It was published independently by Adrian Bowyer and David Watson in 1981 and is one of the most widely used practical methods for building Delaunay triangulations in computational geometry software. Its straightforward incremental structure makes it easy to implement, though naive implementations run in O(n squared) time in the worst case.
Facts
Time ComplexityO(N log N) typical, O(N squared) in degenerate cases 1 Credited ToAdrian Bowyer and David Watson (1981) 1 Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Wikipedia: Bowyer-Watson algorithm
Sources
1. Wikipedia: Bowyer-Watson algorithm
Lead section
can take O(N log N) operations to triangulate N points, although special degenerate cases exist where this goes up to O(N2).
History
Adrian Bowyer and David Watson devised it independently of each other at the same time, and each published a paper on it in the same issue of The Computer Journal
In Field: Algorithms and Complexity Theory, Lead sentence
Bowyer-Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.