Bowyer–Watson algorithm: Difference between revisions

Revision as of 05:45, 9 August 2011

Revision as of 11:21, 4 December 2011

Line 1:

In [[computational geometry]], the '''Bowyer–Watson algorithm''' is a method for computing the [[Delaunay triangulation]] of a finite set of points in any number of [[dimension]]s. The algorithm can be used to obtain a [[Voronoi diagram]] of the points, which is the dual graph of the Delaunay triangulation.

The Bowyer-Watson algorithm is an incremental: italgorithm. 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[[star-shaped polygon]]al 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).