On visibility problems in the plane - Solving minimum vertex guard problems by successive approximations
Conference
Tomás, AP, Bajuelos, AL, Marques, F. (2006). On visibility problems in the plane - Solving minimum vertex guard problems by successive approximations
.
Tomás, AP, Bajuelos, AL, Marques, F. (2006). On visibility problems in the plane - Solving minimum vertex guard problems by successive approximations
.
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.
