Bowyer–Watson algorithm

In computational geometry, the Bowyer–Watson algorithm is a method for computing the Voronoi diagram of a finite set of points in any number of dimensions. The algorithm is incremental: it works by adding points one at a time to a correct Voronoi diagram of a subset of the desired points.

The algorithm is sometimes known just as the Bowyer Algorithm or the Watson Algorithm. 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 (see below).

See also

• Fortune's algorithm
• Delaunay triangulation
• Computational geometry

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.
• Henrik Zimmer, Voronoi and Delaunay Techniques, lecture notes, Computer Sciences VIII, RWTH Aachen, 30 July 2005.