##
Computing Voronoi Skeletons of a 3-D Polyhedron by Space Subdivision

We tackle the problem of computing the Voronoi diagram of a linear 3-D polyhedron.
The main difficulty with the computation is that the diagram's edges and
vertices are of relatively high algebraic degrees.
As a result, previous approaches to the problem have been non-robust,
difficult to implement, or not provenly correct.
We introduce three new proximity skeletons related to the Voronoi diagram:
(1) the *Voronoi Graph (VG)*,
which contains the complete symbolic information of
the Voronoi diagram without containing any geometry;
(2) the *Approximate Voronoi Graph (AVG)*,
which deals with degenerate diagrams by
collapsing sub-graphs of the VG into single nodes;
and
(3) the *Proximity Structure Diagram (PSD)*,
which enhances the VG with a geometric
approximation of Voronoi elements to any desired accuracy.
The new skeletons are important for both theoretical and
practical reasons.
Many applications that extract the proximity information of the
object from its Voronoi diagram can use the Voronoi graphs or the PSD instead.
In addition, the skeletons can be used as initial structures for a
robust and efficient global or local computation of the Voronoi diagram.

We present a space subdivision algorithm to construct the new skeletons,
having three main advantages.
First, it solves at most uni-variate quartic polynomials.
This stands in sharp contrast to previous approaches, which require the
solution of a non-linear tri-variate system of equations.
Second, the algorithm enables purely local computation of the skeletons
in any limited region of interest.
Third, the algorithm is simple to implement.

* Computational Geometry: Theory and Applications, * 21(3):87-120, March 2002.