2026-07-22T21:03:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6802 2024-03-06T10:38:55Z ddc:004 open_access

Universal Guard Problems Fekete, Sándor P. Li, Qian Mitchell, Joseph S. B. Scheffer, Christian Art Gallery Problem universal guarding polygonization worst-case bounds robust covering We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor P. Fekete and Qian Li and Joseph S. B. Mitchell and Christian Scheffer 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.32 urn:nbn:de:0030-drops-68022 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode