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 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
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.