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 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
View the SourceReader 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.