A More Accurate Metaheuristic Approach for the Art Gallery Problem
Open Access
- 23 April 2025
- journal article
- Published by Universal Wiser Publisher Pte. Ltd in Contemporary Mathematics
- p. 2493-2507
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.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Minimum landmarks for robot localization in orthogonal environmentsEvolutionary Intelligence, 2021
- A novel pose estimation algorithm for robotic navigationRobotics and Autonomous Systems, 2015
- Facets for Art Gallery ProblemsAlgorithmica, 2014
- LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONSInternational Journal of Computational Geometry & Applications, 2010
- On guarding the vertices of rectilinear domainsComputational Geometry, 2007
- Computational complexity of art gallery problemsIEEE Transactions on Information Theory, 1986
- An alternate proof of the rectilinear art gallery theoremJournal of Geometry, 1983
- Traditional Galleries Require Fewer WatchmenSIAM Journal on Algebraic Discrete Methods, 1983
- A linear algorithm for computing the visibility polygon from a pointJournal of Algorithms, 1981
- A combinatorial theorem in plane geometryJournal of Combinatorial Theory, Series B, 1975