Chwa, Kyung-YongJo, Byung-CheolKnauer, ChristianMoet, EstherOostrum, René vanShin, Chan-Su2017-03-062017-03-062004Chwa, 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.http://hdl.handle.net/11441/55350Let 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.application/pdfengAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/conferenceObjectinfo:eu-repo/semantics/openAccess