Cover Image

Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abrahamsen, Mikkel, Buchin, Kevin, Buchin, Maike, Kleist, Linda, Löffler, Maarten, Schlipf, Lena, Schulz, André, Stade, Jack
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Bicriteria approximation for minimum dilation graph augmentation
by: Buchin, Kevin, et al.
Published: (2024)

Faster Fréchet Distance under Transformations
by: Buchin, Kevin, et al.
Published: (2025)

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms
by: Buchin, Kevin, et al.
Published: (2025)

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
by: Buchin, Kevin, et al.
Published: (2026)

Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Map-Matching Queries under Fréchet Distance on Low-Density Spanners
by: Buchin, Kevin, et al.
Published: (2024)

Bounding a Polygon by a Minimum Number of Vertices
by: Abrahamsen, Mikkel, et al.
Published: (2025)

Compatible Triangulations of Simple Polygons
by: Afshani, Peyman, et al.
Published: (2026)

Morphing Planar Graph Drawings Through 3D
by: Buchin, Kevin, et al.
Published: (2022)

Geometric spanners of bounded tree-width
by: Buchin, Kevin, et al.
Published: (2024)

Online Sorting and Translational Packing of Convex Polygons
by: Aamand, Anders, et al.
Published: (2021)

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
by: Stade, Jack
Published: (2022)

Covering and Partitioning Complex Objects with Small Pieces
by: Aamand, Anders, et al.
Published: (2026)

Property Testing of Curve Similarity
by: Afshani, Peyman, et al.
Published: (2025)

Adjacency Graphs of Polyhedral Surfaces
by: Arseneva, Elena, et al.
Published: (2021)

Computing $L_\infty$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
by: Angrick, Sebastian, et al.
Published: (2026)

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
by: Buchin, Kevin, et al.
Published: (2026)

Two Tiling is Undecidable
by: Stade, Jack
Published: (2025)

Oriented Spanners
by: Buchin, Kevin, et al.
Published: (2023)

Ten Problems in Geobotics
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Partitioning a Polygon Into Small Pieces
by: Abrahamsen, Mikkel, et al.
Published: (2022)

Computing Oriented Spanners and their Dilation
by: Buchin, Kevin, et al.
Published: (2024)

Minimum Star Partitions of Simple Polygons in Polynomial Time
by: Abrahamsen, Mikkel, et al.
Published: (2023)

Reconfiguration of Squares Using a Constant Number of Moves Each
by: van der Horst, Thijs, et al.
Published: (2026)

Computing Non-Obtuse Triangulations with Few Steiner Points
by: Abrahamsen, Mikkel, et al.
Published: (2025)

On Small Pair Decompositions for Point Sets
by: Buchin, Kevin, et al.
Published: (2026)

Preprocessing Disks for Convex Hulls, Revisited
by: Löffler, Maarten, et al.
Published: (2025)

NP-membership for the boundary-boundary art-gallery problem
by: Stade, Jack
Published: (2025)

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
by: Abrahamsen, Mikkel, et al.
Published: (2020)

Computing Planar Convex Hulls with a Promise
by: Aghamolaei, Sepideh, et al.
Published: (2026)

Online Packing of Orthogonal Polygons
by: Gerlach, Tim, et al.
Published: (2026)

Garment numbers of bi-colored point sets in the plane
by: Aichholzer, Oswin, et al.
Published: (2026)

Clustering with Few Disks to Minimize the Sum of Radii
by: Abrahamsen, Mikkel, et al.
Published: (2023)

On the Connectivity of the Flip Graph of Plane Spanning Paths
by: Kleist, Linda, et al.
Published: (2024)

Minimum Monotone Spanning Trees
by: Di Giacomo, Emilio, et al.
Published: (2024)

Augmenting Plane Straight-Line Graphs to Meet Parity Constraints
by: Christiansen, Aleksander Bjørn Grodt, et al.
Published: (2025)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4
by: Löffler, Maarten, et al.
Published: (2024)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)