Fortune's algorithm

Fortune's algorithm

Fortune's algorithm is a plane sweep algorithm for generating a Voronoi diagram from a set of points in a plane using O("n" log "n") time and O("n") space. [cite book|author = Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf | year = 2000 | title = Computational Geometry | publisher = Springer-Verlag | edition = 2nd revised edition | id = ISBN 3-540-65620-0 Section 7.2: Computing the Voronoi Diagram: pp.151–160.] [citation|title=Voronoi Diagrams and a Day at the Beach|url=http://www.ams.org/featurecolumn/archive/voronoi.html|first=David|last=Austin|publisher=American Mathematical Society|series=Feature Column.] It was originally published by Steven Fortune in 1986 in his "A sweepline algorithm for Voronoi diagrams." [Steven Fortune. A sweepline algorithm for Voronoi diagrams. "Proceedings of the second annual symposium on Computational geometry". Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN:0-89791-194-6. [http://portal.acm.org/citation.cfm?id=10549 ACM Digital Library] [http://www.springerlink.com/content/n88186tl165168rw/ SpringerLink] ]

The algorithm maintains both a sweep line and a "beach line", which both move through the plane as the algorithm progresses. The sweep line is a straight line, which we may by convention assume to be horizontal and moving downwards across the plane. At any time during the algorithm, the input points above the sweep line will have been incorporated into the Voronoi diagram, while the points below the sweep line will not have been considered yet. The beach line is not a line, but a complex curve above the sweep line, composed of pieces of parabolae; it divides the portion of the plane within which the Voronoi diagram can be known, regardless of what other points might be below the sweep line, from the rest of the plane. For each point "p" above the sweep line, one can define a parabola of points equidistant from that point and from the sweep line; the beach line is the lower envelope (pointwise minimum) of these parabolae. As the sweep line progresses, the vertices of the beach line, at which two parabolae cross, trace out the edges of the Voronoi diagram.

The algorithm maintains as data structures a binary search tree describing the combinatorial structure of the beach line, and a priority queue listing potential future events that could change the beach line structure. These events include the addition of another parabola to the beach line (when the sweep line crosses another input point) and the removal of a curve from the beach line (when the sweep line becomes tangent to a circle through some three input points whose parabolae form consecutive segments of the beach line). Each such event may be prioritized by the "y"-coordinate of the sweep line at the point the event occurs. The algorithm itself then consists of repeatedly removing the next event from the priority queue, finding the changes the event causes in the beach line, and updating the data structures. As there are O("n") events to process (each being associated with some feature of the Voronoi diagram) and O(log "n") time to process an event (each consisting of a constant number of binary search tree and priority queue operations) the total time is O("n" log "n").

References

External links

* [http://www.diku.dk/hjemmesider/studerende/duff/Fortune/ Java interactive visual implementation of Fortune's algorithm]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • 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 …   Wikipedia

  • Paper fortune teller — An elaborately decorated fortune teller. A fortune teller (also called a cootie catcher,[1][2] chatterbox,[3] …   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 algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   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

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Mesh generation — is the practice of generating a polygonal or polyhedral mesh that approximates a geometric domain. The term grid generation is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as… …   Wikipedia

  • Closest pair of points problem — Closest pair of points shown in red The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. Its two… …   Wikipedia

  • Daisuke Asakura — Birth name 浅倉大介 Asakura Daisuke Also known as DA, Dai chan (大ちゃん), Scorpion Born November 4, 1967 (1967 11 04) (age 44) …   Wikipedia

  • Voynich manuscript — The Voynich manuscript is a mysterious illustrated book written in an indecipherable text. It is thought to have been written between 1450 and 1520. The author, script and language of the manuscript remain unknown.Over its recorded existence, the …   Wikipedia

Share the article and excerpts

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