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: