Manhattonian Proximity in a Simple Polygon

Klein, Rolf GND; Lingas, Andrzej GND

Let P be a simple planar polygon. We present a linear worst-ca.se time algorithm for constructing the bounded Voronoi diagram of P in the Manhattan metric, where each point z in Pbelongs to the region of the closest vertex of P that is visible from z. Among other consequences, the minimal spanning tree of the vertices in the Manhattan metric that is contained in P can be computed within optimal linear time.

Vorschau

Zitieren

Zitierform:

Klein, Rolf / Lingas, Andrzej: Manhattonian Proximity in a Simple Polygon. 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