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 and is attributed to Sharir [21]. As the art gallery problem is
∃R-complete [3], 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 visionstability δ 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 visionstable. 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 visionstable algorithm and show its practical performance is slower, but comparable with other state of
the art algorithms. 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 parametrized by the chordvisibility width. Furthermore, the one-shot algorithm runs in FPT time, when parametrized
by the number of reflex vertices. These are the first two FPT algorithms for the art gallery
problem.
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 and is attributed to Sharir [21]. As the art gallery problem is
∃R-complete [3], 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 visionstability δ 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 visionstable. 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 visionstable algorithm and show its practical performance is slower, but comparable with other state of
the art algorithms. 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 parametrized by the chordvisibility width. Furthermore, the one-shot algorithm runs in FPT time, when parametrized
by the number of reflex vertices. These are the first two FPT algorithms for the art gallery
problem.
| Original language | English |
|---|---|
| Publisher | arXiv |
| Number of pages | 40 |
| DOIs | |
| Publication status | Published - 2020 |
Publication series
| Name | CoRR |
|---|