DSpace
 
  Repositório Institucional da Universidade de Aveiro > Escola Superior de Tecnologia e Gestão de Águeda > ESTGA - Comunicações >
 On Visibility Problems in the Plane - Solving Minimum Vertex Guards by Successive Approximations
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/8932

title: On Visibility Problems in the Plane - Solving Minimum Vertex Guards by Successive Approximations
authors: Ana Paula Tomás
António Leslie Bajuelos
Fábio Marques
issue date: Jan-2006
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.
URI: http://hdl.handle.net/10773/8932
publisher version/DOI: http://anytime.cs.umass.edu/aimath06/
source: Ninth International Symposium on Artificial Intelligence and Mathematics
appears in collectionsESTGA - Comunicações

files in this item

file description sizeformat
2006 AIMATH apt-alb-fm.pdf535.19 kBAdobe PDFview/open
statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2