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.
A More Accurate Metaheuristic Approach for the Art Gallery Problem
Padkan N.
2025-01-01
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.File | Dimensione | Formato | |
---|---|---|---|
document (3).pdf
accesso aperto
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
1.52 MB
Formato
Adobe PDF
|
1.52 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.