A Linear Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon

Klein, Rolf GND; Lingas, Andrzej GND

For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P. A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P's vertices that is contained in P.

Vorschau

Zitieren

Zitierform:

Klein, Rolf / Lingas, Andrzej: A Linear Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon. Hagen 1993. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe