Randomized Incremental Construction of Simple Abstract Voronoi Diagrams in 3-space

Lê, Ngoc-Minh

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 [7]. 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.

Vorschau

Zitieren

Zitierform:

, Ngoc-Minh: Randomized Incremental Construction of Simple Abstract Voronoi Diagrams in 3-space. Hagen 1995. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe