{"ID":2846387,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.02960","arxiv_id":"2511.02960","title":"The Contiguous Art Gallery Problem is in Θ(n log n)","abstract":"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)$.","short_abstract":"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$. Unl...","url_abs":"https://arxiv.org/abs/2511.02960","url_pdf":"https://arxiv.org/pdf/2511.02960v5","authors":"[\"Sarita de Berg\",\"Jacobus Conradi\",\"Ivor van der Hoog\",\"Eva Rotenberg\"]","published":"2025-11-04T20:01:54Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}