Voronoi diagram of a convex polyhedron
In this little blog article, we will show how the Voronoi diagram of a convex polyhedron in dimensional Euclidean space can be computed in time. As the attentive reader might guess by the time complexity, this is done by intersecting halfspaces in .
Preliminiaries. The Voronoi diagram of sites^{1} tessellates space into socalled Voronoi cells, each of which consisting of those loci that are closer to the defining site than to any other. When we speak of the Voronoi diagram of a polyhedron , then we consider the set of faces of as the set of sites. Also, we are here only interested in the Voronoi diagram within .^{2} Below we see the Voronoi diagram (blue) of a polygon (black), i.e., a polyhedron in the plane:
Each face of has a Voronoi cell that is bounded by blue lines and its defining site (as we restricted the Voronoi diagram to ). The Voronoi diagram consists of loci that are equidistant to two sites. Hence, it is made of pieces of straight lines and parabolas in the plane, resp. quadrics in higherdimensional space.
Convex polyhedra. The Voronoi cells of the convex vertices are collapsed to a point. This observation can be generalized:
Lemma. If is a convex polyhedron^{3} then only its facets^{4} have Voronoi cells with nonempty interior.
Proof. Consider a point in the interior of . It suffices to show that all closest^{5} faces of to are facets. Assume to the contrary that is closest and dimensional, with , and let be the distance. Then the ball centered at and with radius does not intersect in its interior, but touches in a point . Hence, a local neighborhood at on is contained in the tangential hyperplane at on . In other words, is flat, which is a contradiction.
From this lemma it follows that we only need to consider the facets of in order to determine its Voronoi diagram. A point belongs to the facet that minimizes its orthogonal^{6} distance to . Let denote the orthogonal distance of to and let . The point belongs to the Voronoi cell of if . That is, the function graph of is piecewise linear and projecting its faces onto gives the set of Voronoi cells resp. the Voronoi diagram of . Also note that each Voronoi cell is a convex polyhedron itself.
Algorithm. Let us consider for each the halfspace in that contains and whose boundary supports the function graph of . Computing the function graph of is equivalent to intersecting the halfspaces . Using duality between points and hyperplanes, the convex hull algorithm by Chazelle^{7} solves this problem in optimal time.
Concluding remarks.
As a side product, one obtains that the combinatorial size of the Voronoi
diagram is at most . For convex
polyhedra, the straight
skeleton, Voronoi diagram
and medial axis are equal. In fact,
the above technique has already been
applied to compute the
straight skeleton in the plane by consider lower envelopes of (partially
defined) linear functions. For straight skeletons of general input, however,
the difficulty is to construct for each linear function its individual domain
such that the lower envelope representation works out. For convex polygons, the
domain becomes trivial, as illustrated above. Also, to compute the Voronoi
diagram of points, Chazelle transforms the problem to intersecting halfspaces.
In fact, it would not be too surprising, if the result mentioned above can
be found somewhere in the literature. If you know of any reference, I would be
glad if you could tell me.
I would like to thank Anna Lubiw for mentioning this problem.
Update. Anna Lubiw informed me that in a technical report Mitra and Hafer^{8} used basically the same technique to solve this problem.

In discrete geometry, typically the Voronoi diagram of a finite point set is considered. In computational geometry, also (generalized) Voronoi diagrams of line segements or circular arcs are of interest, as they possess a vast number of applications. ↩

For convex polyhedra , the Voronoi diagram outside is boring. ↩

A convex polyhedron in dimensional space is the convex hull of finitely many points, or, equivalently, the bounded intersection of finitely many halfspaces. We may assume here that the polyhedron does not reside within a lowerdimensional subspace. Also note that no dimensional face of is flat in the sense that if we take a point of then a local neighborhood of on does not reside within a dimensional subspace. ↩

A facet is a dimensional face. ↩

We consider the infimumdistance between compact point sets. ↩

As we consider convex polyhedra, the infimum distance is equal to the orthogonal distance. ↩

B. Chazzelle, An Optimal Convex Hull Algorithm in Any Fixed Dimension, Discrete Computational Geometry, 10:377409 (1993). ↩

P. Mitra and L. Hafer, Efficient Computation of the Medial Axis, School of Computing Science Simon Fraser University, B.C, Canada, 1998. [link] ↩