| Title: |
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings |
| Authors: |
Abrahamsen, Mikkel; Buchin, Kevin; Buchin, Maike; Kleist, Linda; Löffler, Maarten; Schlipf, Lena; Schulz, André; Stade, Jack; Sub Geometric Computing; Aichholzer, Oswin; Wang, Haitao |
| Publication Year: |
2025 |
| Subject Terms: |
labeled; polygon; reconfiguration; simple polygon; unit disk; unit square; unlabeled; Software |
| Description: |
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 PSPACEcomplete. 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]. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482991 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482991 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.A245F78 |
| Database: |
BASE |