The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON COMPUTERS
Transactions ID Number: 28-593
Full Name: Antonio Leslie Bajuelos Dominguez
Position: Assistant Professor
Age: ON
Sex: Male
Address: Department of Mathematics, University of Aveiro, 3810-193, Aveiro
Country: PORTUGAL
Tel: 234370359
Tel prefix: 351
Fax: 234382014
E-mail address: leslie@ua.pt
Other E-mails: leslie.bajuelos@gmail.com
Title of the Paper: Optimizing the Minimum Vertex Guard Set on Simple Polygons via a Genetic Algorithm
Authors as they appear in the Paper: Antonio L. Bajuelos, Santiago Canales, Gregorio Hernandez, Ana Mafalda Martins
Email addresses of all the authors: leslie@ua.pt, scanales@upcomillas.es, gregorio@fi.upm.es, mafalda.martins@ua.pt
Number of paper pages: 13
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).
Keywords: Computational geometry, Art gallery problems, Visibility, Approximation algorithms, Metaheuristics, Genetic algorithms
EXTENSION of the file: .pdf
Special (Invited) Session: Minimum Vertex Guard problem for orthogonal polygons: a genetic approach
Organizer of the Session: 593-207
How Did you learn about congress:
IP ADDRESS: 84.90.28.180
