Topological art in simple galleries

DOI10.1007/S00454-023-00540-XarXiv2108.04007OpenAlexW3191260606MaRDI QIDQ6204773

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

Publication date: 2 April 2024

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

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,bin P$ 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$.

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of tensor rank
• Guarding galleries and terrains
• Some provably hard crossing number problems
• Axioms and hulls
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Intersection graphs of rays and grounded segments
• Integer realizations of disk and segment graphs
• Efficient guarding of polygons and terrains
• On the Complexity of the Planar Slope Number Problem
• A Vietoris Mapping Theorem for Homotopy
• Computational complexity of art gallery problems
• A linear algorithm for computing the visibility polygon from a point
• An Optimal Algorithm for Computing Visibility in the Plane
• Irrational Guards are Sometimes Needed
• Oriented Matroids
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Smoothing the Gap Between NP and ER
• Complexity of Geometric k-Planarity for Fixed k
• The art gallery problem is ∃ ℝ-complete
• Algorithm 966
• Parameterized Hardness of Art Gallery Problems
• Inapproximability results for guarding polygons and terrains
• The Parameterized Complexity of Guarding Almost Convex Polygons.

Related Items (1)

Representing matroids over the reals is \(\exists \mathbb{R}\)-complete

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