Minimum vertex guard problem for orthogonal polygons: a genetic approach
Antonio L. Bajuelos, Santiago Canales, Gregorio Hernández Peñalver, Ana Mafalda Martins · International Conference on Mathematical methods, Computational techniques and Intelligent systems · 2008
The problem of minimizing the number of guards placed on vertices needed to guard a given simple polygon (MINIMUM VERTEX GUARD problem) is NP-hard. This computational complexity opens two lines of in vestigation: the development of algorithms that determine approximate solutions and the determination of optimal solutions for special classes of simple polygons. In this paper we follow the first line of investigation proposing an approximation algorithm based on the general metaheuristic Genetic Algorithms to solve the MINIMUM VERTEX GUARD problem.