Bowyer-Watson algorithm

Bowyer-Watson algorithm

In computational geometry, the Bowyer–Watson algorithm is a method for computing the Voronoi diagram of a finite set of points in any number of dimensions. The algorithm is incremental: it works by adding points one at a time to a correct Voronoi diagram of a subset of the desired points.

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

* Fortune's algorithm
* Delaunay triangulation
* Computational geometry

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Adrian Bowyer — is a British engineer and mathematician, currently a lecturer at the University of Bath.Born in 1952 in London, Bowyer is the older child of the late Rosemary and John Bowyer; the latter was a writer, painter and one of the founders of… …   Wikipedia

  • Voronoi diagram — The Voronoi diagram of a random set of points in the plane (all points lie within the image). In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Delaunay triangulation — A Delaunay triangulation in the plane with circumcircles shown In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”