Bowyer–Watson algorithm: Difference between revisions

Revision as of 16:42, 14 April 2010

Revision as of 05:45, 9 August 2011

Line 1:

In [[computational geometry]], the '''Bowyer–Watson algorithm''' is a method for computing the [[VoronoiDelaunay diagramtriangulation]] of a finite set of points in any number of [[dimension]]s. The algorithm iscan incremental:be itused worksto byobtain addinga points[[Voronoi onediagram]] atof athe timepoints, towhich ais correctthe Voronoidual diagram of a subsetgraph of the desiredDelaunay pointstriangulation.

The Bowyer-Watson algorithm is incremental: 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 marked as invalid. Next the invalid triangles are deleted, leaving a convex polygon hole which is then re-triangulated using the new point.

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