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

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2006

Autores

Tomas, AP (Autor) FCUP; Bajuelos, AL (Autor) Outra; Marques, F (Autor) Outra

Ata de Conferência Internacional

Título: 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

Indexação

ISI Web of Knowledge

Scopus - 8 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica