Kunst! – Exact Algorithms for Art Gallery Variants

This work is supported by the DFG Priority Program 1307: Algorithm Engineering.

The classical Art Gallery Problem (AGP) asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases. For the general problem (in which both the set of possible guard positions and the point set to be guarded are uncountable), neither constant-factor approximation algorithms nor exact solution methods are known.

We develop a primal-dual approach for general art gallery problems in arbitrary polygons with holes, in which guards can be placed anywhere, such that the entire interior of the polygon is guarded. Our method computes a sequence of lower and upper bounds on the optimal number of guards until-in case of convergence and integrality-eventually an optimal solution is reached. Our algorithm is based on a formulation of the problem as a (covering) linear program. It solves the problem using a cutting plane and column generation approach, i.e., by solving the primal and dual separation problems. Computational results show the usefulness of our method.

In the "Kunst!" project, we are interested in investigating different aspects of AGP, for example:

• There are some real-world applications relevant to the Art Gallery Problem. These applications come with some additional constraints that are addressed in "Kunst!".
• Integrality of the solutions provided by the primal-dual approach is an essential question. In the basic form of the approach, there is no guarantee on integrality of the optimal solutions. In the project "Kunst!" we improve the primal-dual approach in order to handle this inconvenience.

Theses

Ist hier derzeit keine offene Arbeit zu vergeben? Oder interessiert dich das Projekt, aber es ist einfach nicht das richtige Thema für dich dabei? Dann wende dich einfach direkt an uns! Wir haben laufend Ideen für mögliche Themen in verschiedenen Bereichen, die aber vielleicht im Moment noch nicht zu einer konkreten Aufgabenbeschreibung ausgearbeitet sind. Vielleicht finden wir dann gemeinsam auch für dich eine passende und interessante Aufgabe.

HiWi Jobs

Project members

Publications

• F. Bungiu, M. Hemmer, J. Hershberger, K. Huang and A. Kröller: Efficient Computation of Visibility Polygons, in Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014), March 2014 (BHHHK-texp-2014, BibTeX, http://arxiv.org/abs/1403.3905)
• Sándor P. Fekete, Stephan Friedrichs and Michael Hemmer: Complexity of the General Chromatic Art Gallery Problem, in Proceedings of the 30th European Workshop on Computational Geometry (EuroCG 2014), March 2014 (ffh-cotgcagp-14, BibTeX, http://arxiv.org/abs/1403.2972)
• Jan Kokemüller: Variants of the Art Gallery Problem, Masterarbeit, Technische Universität Carolo-Wilhelmina zu Braunschweig, 2014 (Kokemueller2014, BibTeX)
• Dorit Borrmann, Pedro J. de Rezende, Cid C. de Souza, Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, Andreas Nüchter, Christiane Schmidt and Davi C. Tozoni: Point Guards and Point Clouds: Solving General Art Gallery Problems, in Proceedings of the 29th annual symposium on Symposuim on computational geometry, SoCG '13, Rio de Janeiro, Brazil, pages 347-348, ACM, June 2013 (brsffknst-pgapcsgagp-13, DOI, BibTeX, Video available at http://www.computational-geometry.org/SoCG-videos/socg13video/)
• Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller and Christiane Schmidt: Facets for Art Gallery Problems, in Computing and Combinatorics, Ding-Zhu Du and Guochuan Zhang, Lecture Notes in Computer Science, pages 208-220, Springer Berlin Heidelberg, June 2013 (ffks-ffagp-13b, DOI, BibTeX)
• Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller and Christiane Schmidt: Facets for Art Gallery Problems, in Proceedings of the 29th European Workshop on Computational Geometry (EuroCG 2013), pages 1-4, March 2013 (ffks-ffagp-13a, BibTeX)
• Alexander Kröller, Mahdi Moeini and Christiane Schmidt: A Novel Efficient Approach for Solving the Art Gallery Problem, in WALCOM: Algorithms and Computation, SubirKumar Ghosh and Takeshi Tokuyama, Lecture Notes in Computer Science, pages 5-16, Springer Berlin Heidelberg, February 2013 (kms-aneafstagp-13, DOI, BibTeX)
• Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete and Christiane Schmidt: Exact solutions and bounds for general art gallery problems, in J. Exp. Algorithmics, Vol. 17, No. 1, New York, NY, USA, pages 2.3:2.1-2.3:2.23, ACM, May 2012 (kbfs-esbag-12, BibTeX)
• Alexander Kröller and Christiane Schmidt: Energy-Aware Art Gallery Illumination, in Proceedings of the 28th European Workshop on Computational Geometry, pages 93-96, 2012 (ks-eaagi-12, BibTeX)
• Tobias Baumgartner, Sándor P. Fekete, Alexander Kröller and Christiane Schmidt: Exact Solutions and Bounds for General Art Gallery Problems, in Proceedings of the 2010 Algorithm Engineering and Experiment (ALENEX 10), pages 11-22, SIAM, 2010 (bfks-esbgagp-10, BibTeX)

Further Information

You are welcome to contact the project members for further information.