Memorias de investigación
Artículos en revistas:
Optimizing the Minimum Vertex Guard Set on Simple Polygons via a Genetic Algorithm
Año:2008
Áreas de investigación
  • Matemáticas,
  • Inteligencia artificial
Datos
Descripción
The problem of minimizing the number of vertex-guards necessary to cover a given simple polygon (MINIMUM VERTEX GUARD (MVG) problem) is NP-hard. This computational complexity opens two lines of investigation: the development of algorithms that establish approximate solutions and the determination of optimal solutions for special classes of simple polygons. In this paper we follow the first line of investigation and propose an approximation algorithm based on general metaheuristic genetic algorithms to solve the MVG problem. Based on our algorithm, we conclude that on average the minimum number of vertex-guards needed to cover an arbitrary and an orthogonal polygon with n vertices is n / 6.38 and n / 6.40 , respectively. We also conclude that this result is very satisfactory in the sense that it is always close to optimal (with an approximation ratio of 2, for arbitrary polygons; and with an approximation ratio of 1.9, for orthogonal polygons).
Internacional
Si
JCR del ISI
No
Título de la revista
WSEAS Transactions on Information Science and Applications
ISSN
1790-0832
Factor de impacto JCR
0
Información de impacto
Volumen
5
DOI
Número de revista
11
Desde la página
1584
Hasta la página
1596
Mes
ENERO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Participante: Ana Mafalda Martins Universidade de Aveiro
  • Participante: Antonio Leslie Bajuelos Universidade de Aveiro
  • Autor: Gregorio Hernandez Peñalver UPM
  • Participante: Santiago Canales Universidad Pontificia Comillas de Madrid
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Matemática Aplicada (Facultad de Informática)