Optimizing the Minimum Vertex Guard Set on Simple Polygons via a Genetic Algorithm

Bajuelos Domínguez, Antonio Leslie and Canales Cano, Santiago and Hernández Peñalver, Gregorio and Martins, Ana Mafalda (2008). Optimizing the Minimum Vertex Guard Set on Simple Polygons via a Genetic Algorithm. "Wseas Transactions on Information Science and Applications", v. 5 (n. 11); pp. 1584-1596. ISSN 1790-0832.

Description

Title: Optimizing the Minimum Vertex Guard Set on Simple Polygons via a Genetic Algorithm
Author/s:
  • Bajuelos Domínguez, Antonio Leslie
  • Canales Cano, Santiago
  • Hernández Peñalver, Gregorio
  • Martins, Ana Mafalda
Item Type: Article
Título de Revista/Publicación: Wseas Transactions on Information Science and Applications
Date: November 2008
ISSN: 1790-0832
Volume: 5
Subjects:
Freetext Keywords: Computational geometry, art gallery problems, visibility, approximation algorithms, metaheuristics, genetic algorithms
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 (509kB) | Preview

Abstract

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

More information

Item ID: 3023
DC Identifier: http://oa.upm.es/3023/
OAI Identifier: oai:oa.upm.es:3023
Official URL: http://www.worldses.org/journals/information/information-2008.htm
Deposited by: Memoria Investigacion
Deposited on: 12 May 2010 11:59
Last Modified: 20 Apr 2016 12:36
  • 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