Connecting guards with minimum Steiner points inside simple polygons

摘要

"How many guards are required to cover an art gallery?" asked Victor Klee in 1973, initiated a deep and interesting research area in computational geometry. This problem, referred to as the Art Gallery Problem, has been considered thoroughly in the literature. A recent version of this problem, introduced by Sadhu et al. in CCCG'10, is related to the connectivity of the guards. In this version, for a given set of initial guards inside a given simple polygon, the goal is to obtain a minimum set of new guards, such that the new guards alongside the initial ones have a connected visibility graph. The visibility graph of a set of points inside a simple polygon is a graph whose vertices correspond to the point set and each edge represents the visibility between its endpoints inside the simple polygon. They showed that when the new guards are restricted to the vertices of the polygon, the problem is NP-hard, and proposed an algorithm with logarithmic approximation factor. We show that this problem is NP-Hard in all cases, where the initial guards and the new ones are restricted to vertices, boundary or all points of the polygon. Moreover, we propose constant factor approximation algorithms for all these cases. (C) 2018 Elsevier B.V. All rights reserved.