Topological art in simple galleries

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

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

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

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

Cited In (1)

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

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)