论文标题
一种实用算法，具有艺术画廊问题的性能保证
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
论文作者
论文摘要
考虑到一个封闭的简单多边形$ p $，我们说如果$ p $完全包含段$ pq $，则两个点$ p，q $彼此见。美术馆的问题寻求最小尺寸的$ g \子集p $，完全看到$ p $。当前唯一正确解决美术馆问题的算法准确使用代数方法，并归因于Sharir。由于美术馆的问题是ER完整的，因此无需避免代数方法而没有其他假设，似乎不太可能。在本文中，我们介绍了视力稳定性的概念。为了描述视力稳定性，可以考虑一个增强的后卫，可以看到$δ$的角度或一个较小的后卫，其视力的角度为$δ$“阻止”了反射顶点。 Polygon $ p $具有视力稳定性$δ$，如果以守卫$ p $的最佳增强警卫数量与守卫$ p $的最佳警卫数量相同。我们将争辩说，大多数相关的多边形都是视力稳定的。我们描述了一种单发视觉稳定算法，该算法使用多项式时间计算一个用于视觉台式多边形的最佳防护件，并求解一个整数程序。它保证为每个视力稳定多边形找到最佳解决方案。我们实施了一种迭代视觉刻度算法，并表明其实践性能较慢，但与其他最先进的算法相当。我们的迭代算法受到启发，并紧随单发算法。它延迟了几个步骤，仅在认为必要时才能计算它们。鉴于多边形的和弦$ c $，我们用$ n（c）$表示从$ c $可见的顶点数量。多边形的和弦宽度是所有可能的和弦$ c $的最大$ n（c）$。当通过和弦宽度参数化时，视力稳定多边形允许使用FPT算法。此外，当通过反射顶点的数量参数时，单发算法在fpt时间内运行。
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 $δ$ 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 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.
