Randomized Incremental Construction of Simple Abstract Voronoi Diagrams in 3-space
We introduce the simple abstract Voronoi diagram in 3-space as an abstraction of the usual Voronoi diagram. We show that the 3-dimensional simple abstract Voronoi diagram of n sites can be computed in O(n2) expected time using O(n2) expected space by a randomized algorithm. The algorithm is based on the randomized incremental construction technique of Clarkson and Shor . We apply the algorithm to three concrete types of such diagrams: power diagrams, diagrams under ellipsoid convex distances, and diagrams under the Hausdorff distance for sites that are parallel segments all having the same length.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten