Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
      • Why Braunschweig?
    • During your Studies
      • Fresher's Hub
      • Term Dates
      • Courses
      • Practical Information
      • Beratungsnavi
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Health and Well-being
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni*ae
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
    • Contact
      • Study Service Centre
      • Academic Advice Service
      • Student Office
      • Career Service
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence at TU Braunschweig
      • Research Projects
      • Research Centres
      • Professors‘ Research Profiles
    • Early Career Researchers
      • Support in the early stages of an academic career
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
      • Digital Research Announcement
    • Research Funding
      • Research Funding Network
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • TU Braunschweig Summer School
      • Refugees
      • International Student Support
    • Going Abroad
      • Studying abroad
      • Internships abroad
      • Teaching and research abroad
      • Working abroad
    • International Researchers
      • Welcome Support
      • PhD Studies
      • Service for host institutes
    • Language and intercultural competence training
      • Learning German
      • Learning Foreign Languages
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperations
      • Strategic Partnerships
      • International networks
    • International House
      • About us
      • Contact & Office Hours
      • News and Events
      • International Days
      • 5th Student Conference: Internationalisation of Higher Education
      • Newsletter, Podcast & Videos
      • Job Advertisements
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • The University Development Initiative 2030
      • Foundation University
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Entrepreneurship
      • Friends & Supporters
    • General Public
      • Check-in for Students
      • The Student House
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Services for media
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Executive Board
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Faculty of Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Faculty of Electrical Engineering, Information Technology, Physics
      • Faculty of Humanities and Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • Professional and Personnel Development
      • International House
      • The Project House of the TU Braunschweig
      • Transfer Service
      • University Sports Center
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Services
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR YouTube
    • Facebook
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
Menu
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
  • Current Projects
  • Kunst! – Exact Algorithms for Art Gallery Variants
Logo IBR
IBR Login
  • Institute of Operating Systems and Computer Networks
    • News
    • About us
      • Whole Team
      • Directions
      • Floor Plan
      • Projects
      • Publications
      • Software
      • News Archive
    • Connected and Mobile Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
      • Datasets
    • Reliable System Software
      • Overview
      • Team
      • Teaching
      • Theses & Jobs
      • Research
      • Publications
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2025
      • Winter 2024/2025
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
      • Services Status
    • Spin-Offs
      • Docoloc
      • bliq (formerly AIPARK)
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

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.

Sample gallery
Sample gallery with optimal solution of six guards

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.

Bremen
Optimal Art Gallery solution for the exterior of the Rathaus Bremen

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

No entries found.

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

No entries found.

Project members

NameEMailPhoneRoom
Prof. Dr. Sándor P. Feketes.fekete[[at]]tu-bs.de+49-531-3913111335
Dr. Alexander Kröller
Dr. Christiane Schmidtcschmidt[[at]]ibr.cs.tu-bs.de
Dr. Michael Hemmer
Stephan Friedrichs
Dr. Mahdi Moeini
Dr. Tobias Baumgartner

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.


last changed 2013-10-11, 11:26 (dynamic content) by Stephan Friedrichs

For All Visitors

Vacancies of TU Braunschweig
Career Service' Job Exchange 
Merchandising

For Students

Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard

Internal Tools

Glossary (GER-EN)
Change your Personal Data

Contact

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig

P. O. Box: 38092 Braunschweig
GERMANY

Phone: +49 (0) 531 391-0

Getting here

© Technische Universität Braunschweig
Imprint Privacy Accessibility