A Voronoi diagram divides a plane into regions around a set of seed points, so that every point in a region is closer to its own seed than to any other seed. The regions are called Voronoi cells, and they are convex polygons when the seeds are points in the Euclidean plane. The diagram is the dual of the Delaunay triangulation of the same points, which gives an indirect route to building it: compute the triangulation, then take its dual. Fortune's algorithm constructs the diagram directly in O(n log n) time. The structure is named after Georgy Voronoy, who defined and studied the general n-dimensional case in 1908, and it is also known as Thiessen polygons in rainfall estimation. In computing it appears in robot path planning, and Lloyd's algorithm for clustering uses its construction as a subroutine.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Voronoi diagram (Wikipedia)
In the Other Atlases
Same As
Also in Mathematics Atlas: the same subject.
Sources
1. Voronoi diagram (Wikipedia)
Algorithms
Direct algorithms include Fortune's algorithm, an O(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane.
In Group: Triangulation, Voronoi and Mesh Algorithms, Lead
The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.
In Field: Algorithms and Complexity Theory, Algorithms, construction
Several efficient algorithms are known for constructing Voronoi diagrams, either directly (as the diagram itself) or indirectly by starting with a Delaunay triangulation and then obtaining its dual.
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.