On Visibility Problems in the Plane - Solving Minimum Vertex Guards by Successive Approximations

Abstract

We address the problem of stationing guards in vertices of a simple polygon in such a way that the whole polygon is guarded and the number of guards is minimum. It is known that this is an NP-hard Art Gallery Problem with relevant practical applications. In this paper we present an approximation method that solves the problem by successive approximations, which we introduced in [21]. We report on some results of its experimental evaluation and describe two algorithms for characterizing visibility from a point, that we designed for its implementation.