Show simple item record


dc.creatorChwa, Kyung-Yonges
dc.creatorJo, Byung-Cheoles
dc.creatorKnauer, Christianes
dc.creatorMoet, Estheres
dc.creatorOostrum, René vanes
dc.creatorShin, Chan-Sues
dc.identifier.citationChwa, 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.
dc.description.abstractLet 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
dc.relation.ispartof20th European Workshop on Computational Geometry (2004).
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.titleGuarding art galleries by guarding witnesseses
dc.eventtitle20th European Workshop on Computational Geometryes

Guarding art galleries by guarding ...178.5KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional