Minimum Vertex Guard problem for orthogonal polygons: a genetic approach

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:
  • Bajuelos Domínguez, Antonio Leslie
  • Hernández Peñalver, Gregorio
  • Canales Cano, Santiago
  • Martins, Ana Mafalda
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (186kB) | Preview

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM