Speaker
Description
The Art Gallery problem is a well-known combinatorial optimization problem in computational geometry that seeks to minimize the number of guards required to ensure visibility within a simple polygon. Specifically, the goal is to identify a minimal set of points (guards) within the polygon such that every internal point remains visible to at least one guard. This visibility criterion is established by line segments connecting each point to a guard, all contained within the polygon. In our study, we focus on the variant where guards are selected from the set of polygon vertices. However, finding the optimal guard configuration is NP-hard, necessitating the use of approximation algorithms. To address this problem, we propose a novel approach leveraging deep learning techniques. Specifically, we employ pointer networks, a specialized type of neural network designed for subset selection based on specific criteria.
Our empirical findings demonstrate that our approach achieves near-optimal guard counts for Art Gallery instances consistent with the model’s training data sizes. However, performance deteriorates when dealing with instance sizes larger than those encountered during training.
