Fortune's algorithm constructs the Voronoi diagram of a set of points in the plane in O(n log n) time using a sweep line technique, sweeping a horizontal line down through the plane while maintaining a beach line of parabolic arcs representing the boundary between the swept and unswept regions. Site events, where the sweep line reaches a new point, and circle events, where an arc shrinks to a point, drive the sweep and generate the diagram's edges and vertices. It was published by Steven Fortune in 1986 and remains the standard optimal algorithm for planar Voronoi diagram construction.
Facts
Time Complexity Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Wikipedia: Fortune's algorithm
Sources
1. Wikipedia: Fortune's algorithm
Lead section, publication sentence
It was originally published by Steven Fortune in 1986
Lead section, complexity sentence
time and O(n) space
In Field: Algorithms and Complexity Theory, Lead sentence
Fortune's algorithm is a sweep line 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 Group: Triangulation, Voronoi and Mesh Algorithms, Lead section
for generating a Voronoi diagram from a set of points
View the SourceWikidata: Fortune's Algorithm
Wikidata Q5472844, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.