论文标题
分散美术馆问题
The Dispersive Art Gallery Problem
论文作者
论文摘要
我们介绍了来自安全问题的美术馆问题的新变体。在这种变体中，我们对一组最小的基数不感兴趣，而对这些后卫之间可能距离最大的后卫组。据我们所知，这种变体以前尚未考虑过。我们称其为分散美术馆问题。特别是，在分散美术馆问题中，我们得到了一个多边形$ \ Mathcal {p} $和一个实际数字$ \ ell $，并且想决定$ \ Mathcal {p} $是否具有护罩套件，以至于此组中的每对后卫至少距离$ \ ell ell $相距至少。 在本文中，我们研究了多个群落类别的该问题的顶点后卫变体。我们将矩形的可见性和距离视为$ L_1 $ -METRIC中的大地测量。我们的结果如下。我们给出一个（简单的）稀薄多元，以便每个防护装置的最小成对距离最多为$ 3 $。在正面，我们描述了一种算法，该算法计算匹配该上限的简单多元群落设置，即算法构建了最坏情况最佳解决方案。我们还研究了计算后卫集的计算复杂性，以最大程度地提高后卫组中所有守卫之间的最小距离。我们证明，确定是否存在警卫组，在给定的多莫诺中，所有至少$ 5 $的守卫的最小成对距离是NP的最低距离。我们还能够找到一种最佳的动态编程方法，该方法计算了一个防护套件，该方法可以最大化树状多支着的守卫之间的最小成对距离，即计算最佳解决方案。由于在NP硬度降低中构建的形状也很薄（但有孔），因此该结果完成了薄聚体的情况。
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon $\mathcal{P}$ and a real number $\ell$, and want to decide whether $\mathcal{P}$ has a guard set such that every pair of guards in this set is at least a distance of $\ell$ apart. In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the $L_1$-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most $3$. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least $5$ in a given polyomino is NP-complete. We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.
