Search Results

Documents authored by Stade, Jack

Document
DOI: 10.4230/LIPIcs.SoCG.2025.1
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings

Authors: Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the start configuration to the target configuration while avoiding collisions between the objects and staying within the polygon. Problems of this type have been considered since the early 80s by roboticists and computational geometers. In this paper, we study some of the simplest possible variants where the objects are labeled or unlabeled unit squares or unit disks. In unlabeled reconfiguration, the objects are identical, so that any object is allowed to end at any of the targets positions. In the labeled variant, each object has a designated target position. The results for the labeled variants are direct consequences from our insights on the unlabeled versions. We show that it is PSPACE-hard to decide whether there exists a reconfiguration of (unlabeled/labeled) unit squares even in a simple polygon. Previously, it was only known to be PSPACE-hard in a polygon with holes for both the unlabeled and labeled version [Solovey and Halperin, Int. J. Robotics Res. 2016]. Our proof is based on a result of independent interest, namely that reconfiguration between two satisfying assignments of a formula of Monotone-Planar-3-Sat is also PSPACE-complete. The reduction from reconfiguration of Monotone-Planar-3-Sat to reconfiguration of unit squares extends techniques recently developed to show NP-hardness of packing unit squares in a simple polygon [Abrahamsen and Stade, FOCS 2024]. We also show PSPACE-hardness of reconfiguration of (unlabeled/labeled) unit disks in a polygon with holes. Previously, it was known that unlabeled reconfiguration of disks of two different sizes was PSPACE-hard [Brocken, van der Heijden, Kostitsyna, Lo-Wong and Surtel, FUN 2021].
Cite as

Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade. Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2025.1,
  author =	{Abrahamsen, Mikkel and Buchin, Kevin and Buchin, Maike and Kleist, Linda and L\"{o}ffler, Maarten and Schlipf, Lena and Schulz, Andr\'{e} and Stade, Jack},
  title =	{{Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.1},
  URN =		{urn:nbn:de:0030-drops-231539},
  doi =		{10.4230/LIPIcs.SoCG.2025.1},
  annote =	{Keywords: reconfiguration, unit square, unit disk, unlabeled, labeled, simple polygon, polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.74
The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard

Authors: Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is ∃ℝ-complete, meaning that it is equivalent under polynomial time reductions to deciding whether a system of polynomial equations has a real solution. The art gallery problem asks whether there is a configuration of guards that together can see every point inside of an art gallery modeled by a simple polygon. The original version of this problem (which we call the point-point variant) was shown to be ∃ℝ-hard [Abrahamsen, Adamaszek, and Miltzow, JACM 2021], but the complexity of the variant where guards only need to guard the walls of the art gallery was left as an open problem. We show that this variant is also ∃ℝ-hard. Our techniques can also be used to greatly simplify the proof of ∃ℝ-hardness of the point-point art gallery problem. The gadgets in previous work could only be constructed by using a computer to find complicated rational coordinates with specific algebraic properties. All of our gadgets can be constructed by hand and can be verified with simple geometric arguments.
Cite as

Jack Stade. The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 74:1-74:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{stade:LIPIcs.SoCG.2025.74,
  author =	{Stade, Jack},
  title =	{{The Point-Boundary Art Gallery Problem Is \exists\mathbb{R}-Hard}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{74:1--74:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.74},
  URN =		{urn:nbn:de:0030-drops-232269},
  doi =		{10.4230/LIPIcs.SoCG.2025.74},
  annote =	{Keywords: Art Gallery Problem, Complexity, ETR, Polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.58
Topological Universality of the Art Gallery Problem

Authors: Jack Stade and Jamie Tucker-Foltz

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but holding only up to homotopy equivalence, rather than homeomorphism, and prior to this work, the existence of art galleries even for simple spaces such as the Möbius strip or the three-holed torus were unknown. Our construction relies on an elegant and versatile gadget to copy guard positions with minimal overhead. It is simpler than previous constructions, consisting of a single rectangular room with convex slits cut out from the edges. We show that both the orientable and non-orientable surfaces of genus n admit galleries with only O(n) vertices.
Cite as

Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{stade_et_al:LIPIcs.SoCG.2023.58,
  author =	{Stade, Jack and Tucker-Foltz, Jamie},
  title =	{{Topological Universality of the Art Gallery Problem}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.58},
  URN =		{urn:nbn:de:0030-drops-179082},
  doi =		{10.4230/LIPIcs.SoCG.2023.58},
  annote =	{Keywords: Art gallery, Homeomorphism, Exists-R, ETR, Semi-algebraic sets, Universality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact