Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
    • During your Studies
      • Freshmen-Hub
      • Term Dates
      • Information for Freshman
      • Practical Information
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
      • Team Teaching and Media Education
    • Contact
      • Student Advice Centre
      • Academic Advice Service
      • Admissions Office
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence
      • Research Projects
      • Research Centres
    • Early Stage Researchers
      • Promotion of early career scientists
      • 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
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • Doctorate (PhD)
      • Refugee Students
      • Welcome Programme
      • TU Braunschweig Summer School
    • Scientists
      • Mobile Researchers at the TU Braunschweig
      • Research Services and European Office
    • Language and intercultural competence training
      • Learning German
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperation
    • International House
      • Information for first semester students
      • Contact
      • News and Events
      • Advisory Services
      • Location
      • About us
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Knowledge and Technology Transfer
      • Entrepreneurship
    • General Public
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Communications and Press Service
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Presidency
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Faculty of Humanities and Studies in Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • International House
      • Sports Centre
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • Campus map
    • CloudStorage
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Self-Service
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR Twitter
    • IBR YouTube
    • Facebook
    • Twitter
    • Instagram
    • YouTube
    • LinkedIn
Menu
  • Technische Universität Braunschweig
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
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
    • Distributed Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2023
      • Winter 2022/2023
      • Summer 2022
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
    • Spin-Offs
      • Docoloc
      • 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 Schmidt
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
ImprintPrivacyAccessibility