Bowyer–Watson algorithm

The algorithm of Bowyer/Watson falls into the category of incremental insertion algorithms. Most often the algorithm is know as just the Watson algorithm. If we are not given an initial triangulation it starts by forming the super triangle enclosing the vertex set V that we want to triangulate. The algorithm then proceeds by incrementally inserting the vertices p belongs to V in the triangulation . After every insertion step a search is made, to find the triangles whose circumcircles enclose p. These triangles are deleted, forming a polygon containing p called the insertion polygon. Edges between the vertices of the insertion polygon and p are inserted forming the new triangulation, which is Delaunay . We have now, after inserting all the vertices p belongs to V this way, obtained the Delaunay triangulation Del(V ). In the last step all we need to do is remove the super triangle and its edges going into the triangulation.

Reference

Voronoi and Delaunay Techniques Henrik Zimmer

The Bowyer–Watson algorithm computes the Voronoi diagram of a finite set of points in any number of dimensions. It is named after its inventors, Adrian Bowyer and David F. Watson.

References

• Adrian Bowyer (1981). Computing Dirichlet tessellations, The Computer Journal, 24(2):162–166. doi:10.1093/comjnl/24.2.162.
• David F. Watson (1981). Computing the n-dimensional tessellation with application to Voronoi polytopes, The Computer Journal, 24(2):167–172. doi:10.1093/comjnl/24.2.167.