The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.4 Voronoi Diagrams

Problem Input | Problem Output

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 (C) (rating 10)
  • Qhull - higher dimensional convex hull program (C) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 6)
  • 3D Convex Hull algorithm in Java (Java) (rating 5)
  • CGAL: The Computational Geometry Algorithms Library (C++) (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 Transformation
      
    Triangulation



    This page last modified on 2008-07-10 .
    www.algorist.com