Bowyer–Watson algorithm: Difference between revisions

Revision as of 16:55, 24 January 2008

Revision as of 17:36, 24 January 2008

Line 1:

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

{{context|date=May 2007}}

The '''Bowyer–Watson algorithm''' (or '''Watson algorithm''') computes the [[Voronoi diagram]] of a finite set of points in any number of [[dimension]]s. 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}}.

* Henrik Zimmer, [http://www.henrikzimmer.com/VoronoiDelaunay.pdf Voronoi and Delaunay Techniques], lecture notes, Computer Sciences VIII, RWTH Aachen, 30 July 2005.