Exact algorithm solves guarding problem for weak visibility polygons
Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons
Computational GeometryDiscrete MathematicsData Structures and Algorithms
Summary
The paper addresses a problem called the Art Gallery Problem, which asks how to place the fewest guards to see every part of a shape. The authors focus on a special kind of shape where every point can be seen from some point along one particular edge. They show that placing guards only on this edge makes the problem easier to solve exactly and efficiently. Their method finds the smallest number of guards needed and is faster than previous approaches for related problems.
What this means in practice
- •For robotics navigation teams: Compute minimal sensor placements along fixed routes to fully monitor certain environments with complex shapes.
- •For surveillance system designers: Optimize camera placements along edges in perimeters with limited visibility to reduce equipment costs.
Authors
Shouvik Mondal, Udvas Das, Sasanka Roy
Abstract
The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon. It is $\exists\mathbb{R}$-complete, hence NP-hard. We show that for a particular class of polygons, confining guards to a single edge makes AGP exactly and efficiently solvable. We call this the Strait Guarding Problem (SGP). Its input is a weak visibility polygon (WVP): a simple polygon where every point is seen from some point of one fixed edge, the base. SGP places the fewest guards on the base that jointly see the whole polygon. First, a structural fact: guards on the base edge that cover the boundary already cover the entire interior, turning a two-dimensional covering problem into a one-dimensional one. Our main result is the Witness-Guard Algorithm, which solves SGP exactly in $O((n + \mathrm{OPT} \cdot ρ)(\log n + \log \mathrm{OPT}))$ time, where $ρ$ is the number of reflex vertices in the WVP and OPT is the minimum number of guards. It is output-sensitive and certifies optimality by a witness set of size OPT derived from its output. We also study the guarding-the-vertex version and prove a tight $Θ(n \log n)$ bound, with the lower bound following from Sorting. As a corollary of SGP, we obtain two results for altitude terrain guarding (ATG), a special case that SGP generalizes. We give a linear-time perfect-guarding algorithm, improving the previous $O(n^2 \log n)$ bound of Daescu, Friedrichs, Malik, Polishchuk and Schmidt. We also resolve their problem on the minimum guarding altitude, in $O(nk + k^2 \log k)$ time, improving on the $O(k^2 λ_{k-1}(n) \log n)$ bound of Kang, Kim and Ahn.