
arXiv: 2007.06920
Given a closed simple polygon $P$, we say two points $p,q$ see each other if the segment $pq$ is fully contained in $P$. The art gallery problem seeks a minimum size set $G\subset 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. As the art gallery problem is ER-complete, it seems unlikely to avoid algebraic methods, 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 $\delta$ or a diminished guard whose vision is by an angle of $\delta$ "blocked" by reflex vertices. A polygon $P$ has vision stability $\delta$ 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 visionstable 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-width of a polygon is the maximum $n(c)$ over all possible chords $c$. The set of vision stable polygons admits an FPT algorithm when parametrized by the chord-width. Furthermore, the one-shot algorithm runs in FPT time, when parameterized by the number of reflex vertices.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Art Gallery, Analysis of algorithms and problem complexity, Parameterized complexity, tractability and kernelization, computer science - computational geometry, Computer graphics; computational geometry (digital and algorithmic aspects), Computer Science - Data Structures and Algorithms, QA1-939, computational geometry, existential theory of the reals, discretization, Data Structures and Algorithms (cs.DS), Integer programming, Parametrized complexity, 004, computer science - data structures and algorithms, computer science - discrete mathematics, art gallery problem, Visibility, Computer Science - Computational Geometry, Art gallery, Software, Integer Programming, Mathematics, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Art Gallery, Analysis of algorithms and problem complexity, Parameterized complexity, tractability and kernelization, computer science - computational geometry, Computer graphics; computational geometry (digital and algorithmic aspects), Computer Science - Data Structures and Algorithms, QA1-939, computational geometry, existential theory of the reals, discretization, Data Structures and Algorithms (cs.DS), Integer programming, Parametrized complexity, 004, computer science - data structures and algorithms, computer science - discrete mathematics, art gallery problem, Visibility, Computer Science - Computational Geometry, Art gallery, Software, Integer Programming, Mathematics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
