Polynomial time methods solve witness set problem in weak visibility polygons
Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
Computational GeometryDiscrete MathematicsData Structures and Algorithms
Summary
The paper addresses a puzzle called the Witness Set Problem, which is related to placing guards in rooms so everyone is seen. The authors focus on a special kind of room shape where every point can be viewed from a specific wall. They show how to find the largest group of spots inside the room that guards cannot see together, which helps know how many guards are needed. Their method works efficiently even if witnesses are fixed points or any point inside the room. They also prove that their approach is as fast as possible given the problem's complexity.
What this means in practice
- •For security system designers: Calculate minimal guard deployment in polygonal areas to improve surveillance planning based on exact witness set computations.
- •For robotics navigation teams: Optimize robot sensor placement strategies in buildings modeled as weak visibility polygons using polynomial-time witness set solutions.
Authors
Udvas Das, Shouvik Mondal, Sasanka Roy
Abstract
In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and Packer, is a natural dual to the AGP. In this paper, we study the WSP in weak visibility polygons (WVPs), the simple polygons in which every point is seen from some point of one fixed edge. A witness set is a set of points whose visibility regions are pairwise disjoint, so that no single guard sees two of them. A maximum witness set, therefore, lower-bounds the guard number. Exact polynomial-time algorithms for the WSP are known only for monotone mountains, a proper subclass of WVPs. We give the first exact polynomial-time algorithms for the WSP in WVPs, in two settings. In the Discrete Witness Set Problem (DiscWSP), the witnesses come from a given set of $m$ points, and we find a maximum witness subset in $O(n + m \log(n+m))$ time on an $n$-vertex polygon. The algorithm rests on a structural fact: the visibility intersection graph of a WVP, in which two points are adjacent if their visibility regions intersect, is a trapezoid graph, that is, an intersection graph of trapezoids between two parallel lines. Moreover, the class of these graphs properly contains the interval graphs and the permutation graphs, which may be of independent interest in graph theory. We also prove an $Ω(n \log n)$ lower bound in the algebraic decision-tree model for instances with $m = Θ(n)$, so our algorithm for DiscWSP is optimum. In the Continuous Witness Set Problem (ContWSP), a witness may be any point of the polygon, and we give an exact algorithm running in $O(n \log n + ρ^{2}(n + ρ^{2}))$ time, where $ρ$ is the number of reflex vertices.