On visibility problems in the plane - Solving minimum vertex guard problems by successive approximations

• Type: Article in International Conference Proceedings Book
• Date: 2006

Authors

Tomas, AP (Author) FCUP; Bajuelos, AL (Author) Other; Marques, F (Author) Other

Conference proceedings International

Title: 9th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2006

9th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2006

Fort Lauderdale, FL, 4 January 2006 through 6 January 2006

Indexing

ISI Web of Knowledge

Scopus - 8 Citations

Other information

Authenticus ID: P-008-5A8

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific