1.6.4 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
.
Implementations
Fortune's 2D Voronoi diagram code (C) (rating 9)
Qhull - higher dimensional convex hull program (C) (rating 7)
LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
Joseph O'Rourke's Computational Geometry (C) (rating 4)
The Stanford GraphBase (C) (rating 3)
Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 3)
Related Problems
Convex Hull
Nearest Neighbor Search
Point Location
Medial-Axis Transformation
Triangulation
Go to the corresponding chapter in the book
About the Book
Send us Mail
Go to Main Page
This page last modified on Tue Jun 03, 1997
.