**
Optimal Voronoi diagram construction with ***n*
convex sites in three dimensions
Lee and Drysdale and Sharir have given suboptimal
algorithms (*n *log^{2}*n*)
for computing the Voronoi diagrams of
line-segments or discs in the plane.
This paper adapts their methods to constructing the Voronoi
diagram for
disjoint convex sites in three dimensions.

Let *C(n)* be an upper bound on the number of features in any
diagram involving *n* sites in three dimensions.
Even for point sites, *C(n)* can be proportional to
*n*^{2}, so it is reasonable to assume that
*C(n)/n*^{2} is monotonically nondecreasing.
Under this assumption, our construction
with *n* sites takes optimal time *O(C(n)).*
Results of Aurenhammer's and Chazelle's show that if the
sites are spherical then the diagram can be constructed
in time O(*n*^{2}), but
*C(n)* has yet to be determined for more general classes
of site.
The sites are assumed to be compact and
semi-algebraic of bounded algebraic complexity.
For the sake of simplicity
we assume that the sites are strictly
convex and
rounded (having no sharp corners nor edges).
Assuming strict convexity simplifies the analysis,
as does the roundedness assumption, though
the latter is neither necessary nor restrictive.