An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem

Abstract

In this paper, we propose an exact algorithm to solve the orthogonal art gallery problem in which guards can only be placed on the vertices of the polygon P representing the gallery. Our approach is based on a discretization of P into a finite set of points in its interior. The algorithm repeatedly solves an instance of the set cover problem obtaining a minimum set Z of vertices of P that can view all points in the current discretization. Whenever P is completely visible from Z, the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach 0(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ), our computational experiments reveal that, in practice, they are linear in n and, for n les 200, they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, 0(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ), compared to the possible O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ) atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described.