Revision as of 03:03, 28 December 2011 edit Michael Hardy (talk \| contribs) Administrators 210,577 edits No edit summary ← Previous edit		Revision as of 03:03, 28 December 2011 edit undo Michael Hardy (talk \| contribs) Administrators 210,577 edits mNo edit summary Next edit →
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~~Bowyer–Watson algorithm is an incremental algorithm. 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 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).

Bowyer–Watson algorithm: Difference between revisions