Estimating the Maximum Hidden Vertex Set in Polygons

Bajuelos Domínguez, Antonio Leslie and Hernández Peñalver, Gregorio and Canales Cano, Santiago and Martins, Ana Mafalda (2008). Estimating the Maximum Hidden Vertex Set in Polygons. In: "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.

Description

Title: Estimating the Maximum Hidden Vertex Set in Polygons
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: International Conference on Computational Sciences and Its Applications, ICCSA 2008
Event Dates: 30/06/2008-03/07/2008
Event Location: Perugia, Italia
Title of Book: Proceedings of the International Conference on Computational Sciences and Its Applications, ICCSA 2008
Date: 2008
ISBN: 978-0-7695-3243-1
Subjects:
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 (387kB) | Preview

Abstract

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 .

More information

Item ID: 4561
DC Identifier: http://oa.upm.es/4561/
OAI Identifier: oai:oa.upm.es:4561
DOI: 10.1109/ICCSA.2008.19
Official URL: http://www2.mat.ua.pt/leslie/Papers/EstimatingMHVS.pdf
Deposited by: Memoria Investigacion
Deposited on: 15 Oct 2010 11:26
Last Modified: 20 Apr 2016 13:43
  • 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