The Two Guards Problem

Icking, Christian; Klein, Rolf GND

Given a simple polygon in the plane with two distinguished vertices, s and g, is it possible for two guards to simultaneously walk along the two boundary chains from s to g in such a way that they are always mutually visible? We decide this question in time 0(n log n) and in linear space, where n is the number of edges of the polygon. Moreover, we compute a walk of minimum length within time O(n log n + k), where k is the size of the output, and we prove that this is optimal.

Vorschau

Zitieren

Zitierform:

Icking, Christian / Klein, Rolf: The Two Guards Problem. 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