Memorias de investigación
Ponencias en congresos:
Estimating the Maximum Hidden Vertex Set in Polygons
Año:2008
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
It is known that the MAXIMUM HIDDEN VERTEX SET problem on a given simple polygon is NP-hard [11], therefore we focused on the development of approximation algorithms to tackle it. We propose four strategies to solve this problem, the first two (based on greedy constructive search) are designed specifically to solve it, and the other two are based on the general metaheuristics Simulated Annealing and Genetic Algorithms. We conclude, through experimentation, that our best approximate algorithm is the one based on the Simulated Annealing metaheuristic. The solutions obtained with it are very satisfactory in the sense that they are always close to optimal (with an approximation ratio of 1.7, for arbitrary polygons; and with an approximation ratio of 1.5, for orthogonal polygons). We, also, conclude, that on average the maximum number of hidden vertices in a simple polygon (arbitrary or orthogonal) with n vertices is n/4 .
Internacional
Si
Nombre congreso
International Conference on Computational Sciences and Its Applications (ICCSA 2008)
Tipo de participación
960
Lugar del congreso
Perugia
Revisores
Si
ISBN o ISSN
978-0-7695-3243-1
DOI
dx.doi.org/10.1109/ICCSA.2008.19
Fecha inicio congreso
30/06/2008
Fecha fin congreso
03/07/2008
Desde la página
421
Hasta la página
432
Título de las actas
proceedings of the International Conference on Computational Sciences and Its Applications (ICCSA 2008)
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)