2021-01-26T03:06:56Z
http://oa.upm.es/cgi/oai2
oai:oa.upm.es:4561
2016-04-20T13:43:49Z
7374617475733D707562
7375626A656374733D696E666F726D6174696361
747970653D636F6E666572656E63655F6974656D
Estimating the Maximum Hidden Vertex Set in Polygons
Bajuelos Domínguez, Antonio Leslie
Hernández Peñalver, Gregorio
Canales Cano, Santiago
Martins, Ana Mafalda
Computer Science
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 .
Facultad de Informática (UPM)
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
2008
info:eu-repo/semantics/conferenceObject
Presentation at Congress or Conference
Proceedings of the International Conference on Computational Sciences and Its Applications, ICCSA 2008 | International Conference on Computational Sciences and Its Applications, ICCSA 2008 | 30/06/2008-03/07/2008 | Perugia, Italia
PeerReviewed
application/pdf
eng
http://www2.mat.ua.pt/leslie/Papers/EstimatingMHVS.pdf
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/altIdentifier/doi/10.1109/ICCSA.2008.19
http://oa.upm.es/4561/