Minimum Vertex Guard problem for orthogonal polygons: a genetic approach

Bajuelos Domínguez, Antonio Leslie; Hernández Peñalver, Gregorio; Canales Cano, Santiago y Martins, Ana Mafalda (2008). Minimum Vertex Guard problem for orthogonal polygons: a genetic approach. En: "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.

Descripción

Título: Minimum Vertex Guard problem for orthogonal polygons: a genetic approach
Autor/es:
  • Bajuelos Domínguez, Antonio Leslie
  • Hernández Peñalver, Gregorio
  • Canales Cano, Santiago
  • Martins, Ana Mafalda
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Inteligent Systems, MAMECTIS '08
Fechas del Evento: 26/10/2008-28/10/2008
Lugar del Evento: Corfú, Grecia
Título del Libro: Proceedings of the 10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Inteligent Systems, MAMECTIS '08
Fecha: 2008
ISBN: 978-960-474-012-3
Materias:
Palabras Clave Informales: Art Gallery Problems, Orthogonal Polygons, Metaheuristics, Genetic Algorithms
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (186kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 4599
Identificador DC: http://oa.upm.es/4599/
Identificador OAI: oai:oa.upm.es:4599
URL Oficial: http://www.wseas.org/conferences/2008/corfu/mamectis/
Depositado por: Memoria Investigacion
Depositado el: 13 Oct 2010 10:38
Ultima Modificación: 20 Abr 2016 13:45
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM