Showing 2024Show all
2 papers · 1 filter
cs.CG2024
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two 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 sta…
cs.CG2024
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
Mikkel Abrahamsen, Jack Stade
We show that packing axis-aligned unit squares into a simple polygon is NP-hard, even when is an orthogonal and orthogonally convex polygon with half-integer coordinates. I…