Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
From MaRDI portal
Publication:3512447
DOI10.1007/978-3-540-69903-3_6zbMath1155.68543OpenAlexW1484502988MaRDI QIDQ3512447
Louigi Addario-Berry, Jean-Sébastien Sereni, Omid Amini, Steéphan Thomassé
Publication date: 15 July 2008
Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325147/file/artgallery.pdf
Related Items (4)
The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices ⋮ A note on the perimeter of fat objects ⋮ The fortress problem in terms of the number of reflex and convex vertices. A 3D objects scanning application ⋮ Convex dominating sets in maximal outerplanar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Triangulating and guarding realistic polygons
- A short proof of Chvatal's Watchman Theorem
- Camera placement in integer lattices
- A combinatorial theorem in plane geometry
- Art gallery theorems for guarded guards.
- Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
- Maximizing the guarded boundary of an Art Gallery is APX-complete
- Traditional Galleries Require Fewer Watchmen
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Computational complexity of art gallery problems
- Illumination of convex discs
- Inapproximability results for guarding polygons and terrains
This page was built for publication: Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
