Processing math: 100%

Stony Brook Algorithm Repository


Voronoi Diagrams

Input
Output

Input Description: A set S of points p1,...,pn.
Problem: Decompose the space into regions around each point, such that all the points in the region around pi are closer to pi 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


As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.


Go To Main Page