Facets for art gallery problems

DOI10.1007/s00453-014-9961-xzbMath1330.68302OpenAlexW2106792385MaRDI QIDQ747627

Sándor P. Fekete, Stephan Friedrichs, Christiane Schmidt, Alexander Kröller

Publication date: 19 October 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9961-x

zbMATH Keywords

cutting planesgeometric optimizationart gallery problemfacetsalgorithm engineeringart gallery polytopeset cover polytopesolving NP-hard problem instances to optimality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items (3)

Universal Guard Problems ⋮ Algorithms for art gallery illumination ⋮ Algorithm 966

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS
• Approximation Algorithms for Art Gallery Problems in Polygons and Terrains
• Computational complexity of art gallery problems
• An exact algorithm for minimizing vertex guards on art galleries
• Algorithm 966
• Exact solutions and bounds for general art gallery problems
• Inapproximability results for guarding polygons and terrains

This page was built for publication: Facets for art gallery problems