Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons
Computational Complexity of the Chromatic Art Gallery Problem for Orthogonal Polygons
复制标题
正交多边形的彩色美术馆问题的计算复杂性
DOI：
10.1007/978-3-030-39881-1_13
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ibusuki Tatsuaki
中科院分区：
文献类型：
--
作者：
Iwamoto Chuzo;Ibusuki Tatsuaki
美术馆的问题是找到一组警卫，他们可以一起观察多边形内部的每一个点。我们研究了这个问题的一个色变体，其中每个警卫都被分配了一种不同的颜色。彩色美术馆的问题是为P找到一个警卫组，使两个相同颜色的警卫组不会有重叠的可见区。我们研究了当颜色数为时，具有r-可见性的正交多边形问题的决策形式。在这里，如果包含两个点的最小的轴对齐矩形完全位于多边形内，则这两个点更加明显。本文证明了，当颜色数为时，判定有孔的正多边形是否存在可视保护集，使得不存在两个相同颜色的可视保护区域重叠的可视区域是NP困难的。
The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygonP. We study a chromatic variant of the problem, where each guard is assigned one ofkdistinct colors. Thechromatic art gallery problemis to find a guard set forPsuch that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons withr-visibility when the number of colors is. Here, two points arer-visibleif the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is anr-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is.