论文标题
守护几乎凸多边形的参数化复杂性
The Parameterized Complexity of Guarding Almost Convex Polygons
论文作者
论文摘要
美术馆是计算几何形状中的基本可见性问题。输入由一个简单的多边形P（可能是无限）组成，该集合在p内和整数k内组成。任务是确定大多数K警卫是否可以放在G中的点上，以使C中至少一个后卫可以看到C中的每个点。在艺术画廊的经典表述中，G和C由P中的所有点组成。其他知名变体限制G和C的所有点是P在P边界上的所有点或P的所有位置。 k） - Approximation算法[BONNET和MILTZOW，SOCG'17]，它可能需要非理性的后卫[Abrahamsen等，SocG'17]。在第三个结果的基础上，经典变体和G仅由P边界上的所有点组成的情况都显示为\ [Abrahamsen等人，Stoc'18]。即使G和C仅由P边界上的所有点组成，问题也不在NP中。 鉴于第一个发现，Giannopoulos [Lorentz Center Workshop，2016年]提出了以下问题：Art Gallery FPT是否相对于R，反射顶点的数量？我们专注于g和c是P的所有顶点，称为顶点 - Vertex美术馆。我们表明，Vertex-Vertex艺术画廊可以在时间r^{o（r^2）} n^{o（1）}时解决。我们的方法还延伸到断言，顶点界美术馆和边界Vertex美术馆都是FPT。我们利用“几乎凸多边形”的结构特性来呈现从顶点 - vertex美术馆的两阶段减少到一个新的约束满意度问题（本文也提供了解决方案），其中约束具有Arity 2并涉及单调功能。
Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be \exists R-complete~[Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? We focus on the variant where G and C are all the vertices of P, called Vertex-Vertex Art Gallery. We show that Vertex-Vertex Art Gallery is solvable in time r^{O(r^2)}n^{O(1)}. Our approach also extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT. We utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.
