2025/11/04 by de Berg, Sarita, Conradi, Jacobus, van der Hoog, Ivor +1
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.02960
Recently, a natural variant of the Art Gallery problem, known as the Contiguous Art Gallery problem was proposed. Given a simple polygon P, the goal is to partition its boundary ∂ P into the smallest number of contiguous segments such that each segment is completely visible from some point in P. Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable. At SoCG~2025, three independent works presented algorithms for this problem, each achieving a running time of O(k n5 log n) (or O(n6log n)), where k is the size of an optimal solution. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same asymptotic complexity, suggesting that such a running time might be inherent to the problem. We show that this is not the case. In the real RAM-model, the prevalent model in computational geometry, we present an O(n log n)-time algorithm, achieving an O(k n4) factor speed-up over the previous state-of-the-art. We also give a straightforward sorting-based lower bound by reducing from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in Θ(n log n).