In
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the Bowyer–Watson algorithm is a method for computing the
Delaunay triangulation of a finite set of points in any number of
dimensions. The algorithm can be also used to obtain a
Voronoi diagram of the points, which is the
dual graph of the Delaunay triangulation.
Description
The Bowyer–Watson algorithm is an
incremental algorithm
Increment or incremental may refer to:
* Incrementalism, a theory (also used in politics as a synonym for gradualism)
* Increment and decrement operators, the operators ++ and -- in computer programming
* Incremental computing
* Incremental backu ...
. It works by adding points, one at a time, to a valid Delaunay triangulation of a subset of the desired points. After every insertion, any triangles whose circumcircles contain the new point are deleted, leaving a
star-shaped polygonal hole which is then re-triangulated using the new point. By using the connectivity of the triangulation to efficiently locate triangles to remove, the algorithm can take ''O(N log N)'' operations to triangulate N points, although special degenerate cases exist where this goes up to ''O(N
2)''.
File:Bowyer-Watson 0.png, First step: insert a node in an enclosing "super"-triangle
File:Bowyer-Watson 1.png, Insert second node
File:Bowyer-Watson 2.png, Insert third node
File:Bowyer-Watson 3.png, Insert fourth node
File:Bowyer-Watson 4.png, Insert fifth (and last) node
File:Bowyer-Watson 6.png, Remove edges with extremes in the super-triangle
History
The algorithm is sometimes known just as the Bowyer Algorithm or the Watson Algorithm.
Adrian Bowyer
Adrian Bowyer is an English engineer and mathematician, formerly an academic at the University of Bath.
Born in 1952 in London, Bowyer is the older child of the late Rosemary and John Bowyer; the latter was a writer, painter and one of the fo ...
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).
Pseudocode
The following