Repositorio de producción científica de la Universidad de Sevilla

Guarding art galleries by guarding witnesses


Advanced Search
Opened Access Guarding art galleries by guarding witnesses
Show item statistics
Export to
Author: Chwa, Kyung-Yong
Jo, Byung-Cheol
Knauer, Christian
Moet, Esther
Van Oostrum, René
Shin, Chan-Su
Date: 2004
Document type: Presentation
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 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.
Size: 178.5Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)