Presentation
Guarding art galleries by guarding witnesses
Author/s | Chwa, Kyung-Yong
Jo, Byung-Cheol Knauer, Christian Moet, Esther Oostrum, René van Shin, Chan-Su |
Date | 2004 |
Published in |
|
Abstract | Let P be a simple polygon. We de ne a witness set W to be a set of points su
h that if any (prospective) guard set G guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness ... Let P be a simple polygon. We de ne a witness set W to be a set of points su h that if any (prospective) guard set G guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness set. If a fi nite minimal witness set exists, then it cannot contain any witness in the interior of P ; all witnesses must lie on the boundary of P , and there an be at most one witness in the interior of any edge. We give an algorithm to compute a minimal witness set for P in O(n2 log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline an algorithm that uses a witness set for P to test whether a (prospective) guard set sees all points in P. |
Citation | Chwa, K., Jo, B., Knauer, C., Moet, E., Van Oostrum, R. y Shin, C. (2004). Guarding art galleries by guarding witnesses. En 20th European Workshop on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Guarding art galleries by guarding ... | 178.5Kb | ![]() | View/ | |