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)

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.