Estimating the Maximum Hidden Vertex Set in Polygons

Bajuelos Domínguez, Antonio Leslie; Hernández Peñalver, Gregorio; Canales Cano, Santiago y Martins, Ana Mafalda (2008). Estimating the Maximum Hidden Vertex Set in Polygons. En: "International Conference on Computational Sciences and Its Applications, ICCSA 2008", 30/06/2008-03/07/2008, Perugia, Italia. ISBN 978-0-7695-3243-1. https://doi.org/10.1109/ICCSA.2008.19.

Descripción

Título: Estimating the Maximum Hidden Vertex Set in Polygons
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: International Conference on Computational Sciences and Its Applications, ICCSA 2008
Fechas del Evento: 30/06/2008-03/07/2008
Lugar del Evento: Perugia, Italia
Título del Libro: Proceedings of the International Conference on Computational Sciences and Its Applications, ICCSA 2008
Fecha: 2008
ISBN: 978-0-7695-3243-1
Materias:
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 (387kB) | Vista Previa

Resumen

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 n4 .

Más información

ID de Registro: 4561
Identificador DC: http://oa.upm.es/4561/
Identificador OAI: oai:oa.upm.es:4561
Identificador DOI: 10.1109/ICCSA.2008.19
URL Oficial: http://www2.mat.ua.pt/leslie/Papers/EstimatingMHVS.pdf
Depositado por: Memoria Investigacion
Depositado el: 15 Oct 2010 11:26
Ultima Modificación: 20 Abr 2016 13:43
  • 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