Visibility Extension via Reflection
Preprint
Abstract
This paper studies a variant of the Art-gallery problem in which "walls" can be replaced by \emph{reflecting-edges}, which allows the guard to see further and thereby see a larger portion of the gallery. The art-gallery is a simple closed polygon $P$, a guard is a point $p$ in $P$, and a guard sees another point $q$ in $P$ if the segment $\overline{pq}$ is contained in the interior of $P$. The visibility region of $p$ is the set of points $q$ in $P$ that are visible from $p$. If we let an edge of the polygon allow reflections, then the visibility region should be changed accordingly. We study visibility with specular and diffuse reflections. Moreover, the number of times a ray can be reflected can be taken as a parameter. For \emph{vertex} guarding polygons with $k$ diffuse reflections, we establish an upper bound on the optimum solution. For this problem, we generalize the $O(logn)$-approximation ratio algorithm of the Art Gallery Problem. For a bounded $k$, the generalization gives a polynomial-time algorithm with $O(log n)$-approximation ratio for both cases diffuse and specular reflections. Furthermore, We show that several cases of the generalized problem are NP-hard. We also illustrate that if $P$ is a funnel or a weak visibility polygon, then the problem becomes more straightforward and can be solved in polynomial time.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Visibility extension via mirror-edges to cover invisible segmentsTheoretical Computer Science, 2019
- Visibility-Based Target-Tracking Game: Bounds and Tracking StrategiesIEEE Robotics and Automation Letters, 2017
- How to Extend Visibility Polygons by Mirrors to Cover Invisible Segments2017
- Vertex Guarding in Weak Visibility Polygons2015
- Improved Approximation for Guarding Simple Galleries from the PerimeterDiscrete & Computational Geometry, 2011
- Approximation algorithms for art gallery problems in polygonsDiscrete Applied Mathematics, 2010
- Inapproximability Results for Guarding Polygons and TerrainsAlgorithmica, 2001
- Art Gallery and Illumination Problems2000
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983