4 papers
Reconfiguration of Squares Using a Constant Number of Moves Each
Thijs van der Horst, Maarten Löffler, Tim Ophelders +1
Multi-robot motion planning is a hard problem. We investigate restricted variants of the problem where square robots are allowed to slide over an arbitrary curve to a new position…
Preprocessing Disks for Convex Hulls, Revisited
Maarten Löffler, Benjamin Raichel
In the preprocessing framework one is given a set of regions that one is allowed to preprocess to create some auxiliary structure such that when a realization of these regions is g…
Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
Maarten Löffler, Benjamin Raichel
In the preprocessing framework for dealing with uncertain data, one is given a set of regions that one is allowed to preprocess to create some auxiliary structure such that when a…
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…