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. In Computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface In Mathematics, a Voronoi diagram, named after Georgy Voronoi, also called a Voronoi Tessellation, a Voronoi decomposition, or In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments [1][2] It was originally published by Steven Fortune in 1986 in his "A sweepline algorithm for Voronoi diagrams. "[3]
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. In Mathematics, the parabola (pəˈræbələ from the Greek παραβολή) is a Conic section, the intersection of a right circular 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. In Computer science, a binary search tree ( BST) is a Binary tree Data structure which has the following properties each node A priority queue is an Abstract data type in Computer programming that supports the following three operations InsertWithPriority: add 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
- ^ Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Markus Hendrik Overmars (born 29 September 1958 in Zeist, Netherlands) is a Dutch computer scientist and teacher of games programming Computational Geometry, 2nd revised edition, Springer-Verlag. Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic ISBN 3-540-65620-0. Section 7. 2: Computing the Voronoi Diagram: pp. 151–160.
- ^ Austin, David, Voronoi Diagrams and a Day at the Beach, Feature Column, American Mathematical Society, <http://www.ams.org/featurecolumn/archive/voronoi.html>. The American Mathematical Society (AMS is an association of professional Mathematicians dedicated to the interests of mathematical research and scholarship which
- ^ 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. ACM Digital LibrarySpringerLink
External links
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic