2026-08-18T15:51:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21098 2024-09-23T09:13:16Z ddc:004 open_access

Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof Biniaz, Ahmad Polygon guarding Edge guarding Short proof Simple algorithm O'Rourke (1983) proved that every n-vertex polygon, with n ≥ 4, can be guarded by ⌊ n/4⌋ edges or diagonals - a variant of Chvátal’s theorem for sufficiency of ⌊ n/3⌋ vertices. We present a short proof for a somewhat stronger result that allows us to impose some constraints on the guards. We prove that for every given subset V of vertices, the polygon can be guarded by ⌊(n+2|V|)/4⌋ edges or diagonals that include at least one edge or diagonal incident to every vertex of V. This bound is the best achievable given the constraint for V. Our proof is by induction and suggests a simple linear-time algorithm after triangulating the polygon. The sufficiency of ⌊4⌋ guards is a special case of the new result where V is the empty set. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.27 urn:nbn:de:0030-drops-210989 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode