##
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
.