A More Accurate Metaheuristic Approach for the Art Gallery Problem

Abstract

The Art Gallery problem is one of the most important non-deterministic polynomial (NP)-hard optimization problems in computational geometry, with many applications in localization, robotics, telecommunications, etc. The goal of the Art Gallery problem is to find the minimum number of guards needed within a simple polygon to observe and protect its entirety. There are several approaches to solving the Art Gallery problem, and this paper presents an efficient method based on the Particle Filter algorithm, which solves the most fundamental case of the problem in a nearly optimal manner. Experimental results on random polygons generated show that the new method is more accurate, providing solutions that are, on average, 9.94% better than Bottino's results for the same sample set. The approach was also applied to four groups of random orthogonal polygons and compared with the optimal solution. Results show that the new method finds the optimal solution with a 0.16% error. Furthermore, this paper discusses the impact of resampling and particle numbers in minimizing runtime.