This paper studies local properties of Voronoi
diagrams of sets of disjoint compact convex sites in
It is established that bisectors are C1 surfaces and trisectors are C1 curves, and that as a point moves along a trisector its clearance sphere develops monotonically. This monotonicity property is useful in establishing the existence of Voronoi vertices bounding edges in certain situations.
The paper then considers the diagram for a set of disjoint spheres. Considerations about general position are covered in detail. By letting the spheres grow from point sites till they reach their true radius, it is shown that the Voronoi cell for the smallest site has complexity O(n). assuming that the sites are of at most k distinct radii. It follows that the Voronoi diagram is O(n2).
Although this is weaker than Aurenhammer's result establishing O(n2) complexity with no restriction on radius, the techniques may be of value for studying more general Voronoi diagrams.
Finally, the paper shows that without the bound on the number of different radii, the cell owned by a point site can have complexity at least n2.