Abstract
Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Θ (n) such maximal walks, and we show how to find all of them in O (n log n) time.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 3-11 |
Fachzeitschrift | Computational Geometry: Theory and Applications |
Ausgabenummer | 84 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2019 |