[ACM Press the 25th annual symposium - Aarhus, Denmark (2009.06.08-2009.06.10)] Proceedings of the 25th annual symposium on Computational geometry - SCG '09 - An IP solution to the art gallery problem

✍ Scribed by Couto, Marcelo C.; de Rezende, Pedro J.; de Souza, Cid C.

• Book ID: 121202206
• Publisher: ACM Press
• Year: 2009
• Weight: 569 KB
• Category: Article
• ISBN: 1605585017
• DOI: 10.1145/1542362.1542378

✦ Synopsis

The Art Gallery problem (agp) consists of minimizing the number of guards required to cover a gallery whose boundary is a simple polygon P . In this paper, we describe an Integer Programming based solution to agp that is presented in the accompanying video. Said solution is comprised of an exact algorithm that models discretizations of P as instances of the Set Cover problem and iteratively solves them using an IP solver. We have shown elsewhere [4] that this process always converges. A testing environment, shown in the video, has been implemented with which we have collected substantial experimental evidence that this approach is very efficient in practice, by solving instances of up to 2500 vertices.