Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (186kB) | Preview |
Minimum Vertex Guard problem for orthogonal polygons: a genetic approach
Citation
Bajuelos Domínguez, Antonio Leslie and Hernández Peñalver, Gregorio and Canales Cano, Santiago and Martins, Ana Mafalda (2008). Minimum Vertex Guard problem for orthogonal polygons: a genetic approach. In: "10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Inteligent Systems, MAMECTIS '08", 26/10/2008-28/10/2008, Corfú, Grecia. ISBN 978-960-474-012-3.
Description
| Title: | Minimum Vertex Guard problem for orthogonal polygons: a genetic approach |
|---|---|
| Author/s: |
|
| Item Type: | Presentation at Congress or Conference (Article) |
| Event Title: | 10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Inteligent Systems, MAMECTIS '08 |
| Event Dates: | 26/10/2008-28/10/2008 |
| Event Location: | Corfú, Grecia |
| Title of Book: | Proceedings of the 10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Inteligent Systems, MAMECTIS '08 |
| Date: | 2008 |
| ISBN: | 978-960-474-012-3 |
| Subjects: | |
| Freetext Keywords: | Art Gallery Problems, Orthogonal Polygons, Metaheuristics, Genetic Algorithms |
| Faculty: | Facultad de Informática (UPM) |
| Department: | Matemática Aplicada |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
The problem of minimizing the number of guards placed on vertices needed to guard a given simple polygon (MINIMUM VERTEX GUARD problem) is NP-hard. This computational complexity opens two lines of investigation: the development of algorithms that determine approximate solutions and the determination of optimal solutions for special classes of simple polygons. In this paper we follow the first line of investigation proposing an approximation algorithm based on the general met heuristic Genetic Algorithms to solve the MINIMUM VERTEXGUARD problem.
More information
| Item ID: | 4599 |
|---|---|
| DC Identifier: | https://oa.upm.es/4599/ |
| OAI Identifier: | oai:oa.upm.es:4599 |
| Official URL: | http://www.wseas.org/conferences/2008/corfu/mamectis/ |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 13 Oct 2010 10:38 |
| Last Modified: | 20 Apr 2016 13:45 |
