Stony Brook Algorithm Repository


Voronoi Diagrams

Input
Output

Input Description: A set \(S\) of points \(p_1,...,p_n\).
Problem: Decompose the space into regions around each point, such that all the points in the region around \(p_i\) are closer to \(p_i\) than any other point in \(S\).

Excerpt from The Algorithm Design Manual: Voronoi diagrams represent the region of influence around each of a given set of sites. If these sites represent the locations of McDonald's restaurants, the Voronoi diagram partitions space into cells around each restaurant. For each person living in a particular cell, the defining McDonald's represents the closest place to get a Big Mac.

Voronoi diagrams have a surprising variety of uses:


Implementations

Fortune's 2D Voronoi diagram code (rating 10)
Vorolay (rating 8)
Javascript-Voronoi (rating 8)
QHull (rating 7)
Delaunay_Triangulation (rating 6)
LEDA (rating 6)
CGAL (rating 6)
voronoi (rating 5)
3D Convex Hull algorithm in Java (rating 5)


Recommended Books

Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke Computational Geometry by F. Preparata and M. Shamos

Related Problems


Convex Hull

Nearest Neighbor Search

Point Location

Medial-Axis Transform

Triangulation

Go To Main Page