Solving the Art Gallery Problem using Gradient Descent
Summary
The Art Gallery Problem is one of the central problems in computational geometry. It was recently shown that the problem is ∃R-complete. Thus it is unlikely to be solvable by methods that are usually applied to NP-complete problems. These methods include heuristics with provable guarantees to come as close as possible to the optimal solution in polynomial time. Nonetheless, one of the most important methods to solve ∃R-complete problems is called gradient descent. Curiously, there was no attempt yet to solve the Art Gallery Problem with gradient descent. By aiming to maximise the area seen by the guards in the Art Gallery Problem, we get a continuous cost function, which allows us to compute the gradient. Using the gradient and other heuristics inspired from neural networks, we try to solve the Art Gallery Problem practically using gradient descent. Specifically, we aim to use the library CGAL. Implementations show how feasible this approach is. We visualise the results and discuss the performance of the algorithm on different input shapes and sizes.