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
Author: 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.
Peer review: yes
URI: http://hdl.handle.net/10773/8932
Publisher Version: http://anytime.cs.umass.edu/aimath06/
Appears in Collections:ESTGA - Comunicações

Files in This Item:
File Description SizeFormat 
2006 AIMATH apt-alb-fm.pdf535.19 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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