Abstract
Given a closed simple polygon P, we say two points p, q see each other if the segment seg(p, q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃R-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see “around the corner” by an angle of δ or a diminished guard whose vision is by an angle of δ “blocked” by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.
Original language | English |
---|---|
Pages | 1-16 |
Number of pages | 16 |
DOIs | |
Publication status | Published - 1 Jun 2021 |
Event | 37th International Symposium on Computational Geometry - Duration: 7 Jul 2021 → 11 Jul 2021 |
Conference
Conference | 37th International Symposium on Computational Geometry |
---|---|
Abbreviated title | SoCG |
Period | 7/07/21 → 11/07/21 |
Keywords
- Art gallery
- Integer programming
- Parametrized complexity
- Visibility