The Contiguous Art Gallery Problem is in Θ(n log n)
For computational geometry researchers, this resolves the complexity of the Contiguous Art Gallery problem, proving it is Θ(n log n) and thus not inherently as expensive as earlier algorithms suggested.
The Contiguous Art Gallery problem, previously solved in O(k n^5 log n) time, is now shown to be solvable in O(n log n) time, matching a lower bound of Ω(n log n). This represents an O(k n^4) factor speed-up over prior work.
Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon $P$, the goal is to partition its boundary $\partial 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 n^5 \log n)$ (or $O(n^6\log 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 n^4)$ 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)$.