"The Big Sweep" : On the Power of the Wavefront Approach to Voronoi Diagrams

Dehne, Frank; Klein, Rolf GND

We show that the wavefront approach to Voronoi diagrams ( a deterministic line sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the Euclidean metric. In fact, we provide the first worstcase optimal (O(n logn) time, O(n) space) algorithm that is valid for the full class of what has been called nice metrics in the plane. This also solves the previously open problem of providing an 0( n log n) time plane-sweep algorithm for arbitrary Lk -metrics. Nice metrics include all tractable convex distance functions but also distance measures like the Moscow metric, and composed metrics. The algorithm is conceptually simple, but it copes with all possible deformations of the diagram.

Vorschau

Zitieren

Zitierform:

Dehne, Frank / Klein, Rolf: "The Big Sweep". On the Power of the Wavefront Approach to Voronoi Diagrams. Hagen 1992. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe