## 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 |
---|