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 | Size | Format | |
---|---|---|---|---|
2006 AIMATH apt-alb-fm.pdf | 535.19 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.