Next: Sample session with cdd+ Up: Voronoi Diagram and Delaunay Previous: Sample session with cdd+   Contents

## Is it possible to compute only the adjacencies of Voronoi cells in the Voronoi diagram efficiently?

Yes, it can be done very efficiently by linear programming (LP), and very importantly this can be done for very large scale problems, with practically no bounds on the size with an efficient LP solver.

The method is simple. The lifting technique we described in 3.2 immediately gives the idea. Recall that the Voronoi diagram of a set of points in is the projection of the following -polyhedron to space of the first components.

For simplicity, denote it as

where is a given matrix and is a -vector. Now for each , consider the th facet of :

 and (7)

Two facets and are called adjacent if the intersection is a facet of both, i.e. has dimension . An equivalent definition is: they are adjacent if (*) the facet becomes larger once the facet is removed from the polyhedron, i.e. the th inequality is removed from the system .

It is easy to see that two Voronoi cells and are adjacent if and only if the corresponding facets and are adjacent in the polyhedron . Now, we formulate the following LP for any distinct , :

where is equal to except for th component . The new inequality system is simply a modification of the original system obtained by relaxing the th inequality a little bit. An important remark is, by definition (*), and are adjacent if and only if the objective value is negative at an optimum solution. Thus we formulated the Voronoi adjacency computation as an LP problem.

How much do we gain by using LP for the adjacency computation, instead of computing the whole Voronoi diagram? A lot. It is hard to exaggerate this, because the LP (8) (in fact any LP) is solvable in polynomial time, whereas the associated Voronoi computation is exponential in and . Using the standard simplex method, the time complexity of solving an LP is not polynomial, but the practical complexity is roughly .

Subsections

Next: Sample session with cdd+ Up: Voronoi Diagram and Delaunay Previous: Sample session with cdd+   Contents
Komei Fukuda 2004-08-26