This paper studies a variant of the Art Gallery problem in which the ``walls" can be replaced by \emph{reflecting edges}, which allows the guards to see further and thereby see a larger portion of the gallery. Given a simple polygon $\cal P$, first, we consider one guard as a point viewer, and we intend to use reflection to add a certain amount of area to the visibility polygon of the guard. We study visibility with specular and diffuse reflections where the specular type of reflection is the mirror-like reflection, and in the diffuse type of reflection, the angle between the incident and reflected ray may assume all possible values between $0$ and $\pi$. Lee and Aggarwal already proved that several versions of the general Art Gallery problem are $NP$-hard. We show that several cases of adding an area to the visible area of a given point guard are $NP$-hard, too. Second, we assume all edges are reflectors, and we intend to decrease the minimum number of guards required to cover the whole gallery. Chao Xu proved that even considering $r$ specular reflections, one may need $\lfloor \frac{n}{3} \rfloor$ guards to cover the polygon. Let $r$ be the maximum number of reflections of a guard's visibility ray. In this work, we prove that considering $r$ \emph{diffuse} reflections, the minimum number of \emph{vertex or boundary} guards required to cover a given simple polygon $\cal P$ decreases to { $\bf \lceil \frac{\alpha}{1+ \lfloor \frac{r}{8} \rfloor} \rceil$}, where $\alpha$ indicates the minimum number of guards required to cover the polygon without reflection. We also generalize the $\mathcal{O}(\log n)$-approximation ratio algorithm of the vertex guarding problem to work in the presence of reflection.
翻译:本文研究了艺术馆问题的一种变体,在此变体中,“墙壁”可以由“反射边”代替,这使得守卫能够看得更远,从而看到更多的画廊部分。给定一个简单的多边形 $\cal P$,首先,我们考虑一个警卫作为一个点的观察者,并试图使用反射来增加警卫的可见性边界的一定面积。我们研究了具有镜面反射和漫反射性质的可见性,其中镜面反射类型为镜面反射,而在漫反射类型中,入射光线和反射光线之间的角度可能取 $0$ 到 $\pi$ 之间的所有可能值。Lee 和 Aggarwal 已经证明了一般艺术馆问题的几个版本是 $NP$-难的。我们证明添加到给定点警卫的可见面积的几种情况也是 $NP$-难的。其次,我们假设所有边都是反射器,并且我们打算减少所需的守卫最小数量以覆盖整个画廊。Chao Xu 证明了即使考虑 $r$ 个镜面反射,也可能需要 $\lfloor \frac{n}{3} \rfloor$ 个守卫来覆盖多边形。令 $r$ 为警卫的可见性光线的最大反射次数。在这项工作中,我们证明了,在考虑 $r$ 个漫反射反射的情况下,覆盖给定简单多边形 $\cal P$ 所需的最小顶点或边界守卫数量减少到 {$\bf \lceil \frac{\alpha}{1+ \lfloor \frac{r}{8} \rfloor} \rceil$},其中 $\alpha$ 表示不使用反射所需的最小守卫数量。同时,我们还将顶点守卫问题的 $\mathcal{O}(\log n)$ 近似比算法推广到存在反射的情况。