Content deleted Content added
mNo edit summary |
Minor wikification |
||
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 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.
| |||