Geometry Seminar

---

Eyes Forward: Contiguously Guarding an Art Gallery in Optimal Time

Speaker: Sarita de Berg, IT University of Copenhagen

Location: Online

Date: Tuesday, February 24, 2026, 2 p.m.

Synopsis:

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 \(\partial P\) into the smallest number of contiguous segments such that each segment is completely visible from some point in \(P\) (the guard). 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. 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 lower bound reduction from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in \(\Theta(n \log n)\).

Notes:

On Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.