Topological art in simple galleries

DOI10.1007/S00454-023-00540-XMaRDI QIDQ6204773zbMATH OpenOpenAlexFDO

Authors Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, Simon Weber

Publication date 2 April 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2108.04007

zbMATH Keywords

computational geometryart gallery problemtopological universality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $P$ be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in $P$. We say two points $a,binP$ can see each other if the line segment $seg(a,b)$ is contained in $P$. We denote by $V(P)$ the family of all minimum guard placements. The Hausdorff distance makes $V(P)$ a metric space and thus a topological space. We show homotopy-universality, that is for every semi-algebraic set $S$ there is a polygon $P$ such that $V(P)$ is homotopy equivalent to $S$. Furthermore, for various concrete topological spaces $T$, we describe instances $I$ of the art gallery problem such that $V(I)$ is homeomorphic to $T$.

Recommendations

• Topological art in simple galleries
• Topological universality of the art gallery problem
• Guards, Galleries, Fortresses, and the Octoplex
• scientific article; zbMATH DE number 2163102
• scientific article; zbMATH DE number 4065813

Cites work

• scientific article; zbMATH DE number 3423298 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 3518931 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• A Vietoris Mapping Theorem for Homotopy
• A combinatorial theorem in plane geometry
• A linear algorithm for computing the visibility polygon from a point
• A short proof of Chvatal's Watchman Theorem
• Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
• An Optimal Algorithm for Computing Visibility in the Plane
• An approximation algorithm for the art gallery problem
• Axioms and hulls
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Computational complexity of art gallery problems
• Efficient guarding of polygons and terrains
• Guarding galleries and terrains
• Inapproximability results for guarding polygons and terrains
• Integer realizations of disk and segment graphs
• Intersection graphs of rays and grounded segments
• Irrational guards are sometimes needed
• On the complexity of the planar slope number problem
• Oriented Matroids
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Parameterized Hardness of Art Gallery Problems
• Smoothing the Gap Between NP and ER
• Some provably hard crossing number problems
• The Parameterized Complexity of Guarding Almost Convex Polygons.
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• The complexity of tensor rank
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

Cited in

(3)

• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Topological universality of the art gallery problem
• Topological art in simple galleries

This page was built for publication: Topological art in simple galleries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204773)