2026-07-22T07:15:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23172 2025-10-02T12:41:52Z ddc:004 open_access

Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems Biniaz, Ahmad Maheshwari, Anil Merrild, Magnus Christian Ring Mitchell, Joseph S. B. Odak, Saeed Polishchuk, Valentin Robson, Eliot W. Rysgaard, Casper Moldrup Schou, Jens Kristian Refsgaard Shermer, Thomas Spalding-Jamieson, Jack Svenning, Rolf Zheng, Da Wei Art Gallery Problem Computational Geometry Combinatorics Discrete Algorithms We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz and Anil Maheshwari and Magnus Christian Ring Merrild and Joseph S. B. Mitchell and Saeed Odak and Valentin Polishchuk and Eliot W. Robson and Casper Moldrup Rysgaard and Jens Kristian Refsgaard Schou and Thomas Shermer and Jack Spalding-Jamieson and Rolf Svenning and Da Wei Zheng 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.20 urn:nbn:de:0030-drops-231720 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode