Proposing a New Heuristic Algorithm to Solve Minimum-Vertex Guard in Art-Gallery Problem

Finding minimum vertex guard to cover an art gallery is one of outstanding open problems in computational geometry. In this problem, a given polygonal art gallery is given. The aim is to find minimum vertex guard to cover it. This is a NP-hard problem. The purpose of this paper is to propose a heuristic algorithm that finds minimum number of vertex guard, who is put on the vertex of polygon. This algorithm has been implemented with C#. An arbitrary polygon with n vertices is randomly developed. Computational result of the proposed algorithm shows that the average number of vertex guard needed to cover a polygon with n vertices is n/6.48. This result is better than other algorithms developed for this problem. For this, we finally compare the results of our heuristic algorithm with the result of genetic algorithm and well-known art-gallery theorem.