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.

Studentische Arbeiten

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 Stellen

Projektmitglieder

Veröffentlichungen

• 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), März 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), März 2014 (ffh-cotgcagp-14, BibTeX, http://arxiv.org/abs/1403.2972)
• Jan Kokemüller: Variants of the Art Gallery Problem, Master's Thesis, 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, Seite 347-348, ACM, Juni 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, Seite 208-220, Springer Berlin Heidelberg, Juni 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), Seite 1-4, März 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, Seite 5-16, Springer Berlin Heidelberg, Februar 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, Jg. 17, Nr. 1, New York, NY, USA, Seite 2.3:2.1-2.3:2.23, ACM, Mai 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, Seite 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), Seite 11-22, SIAM, 2010 (bfks-esbgagp-10, BibTeX)

Weitere Informationen

Bei weiteren Fragen wenden Sie sich bitte an die Projektmitglieder.