Paper by Erik D. Demaine
- Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán, “Characterizing Universal Reconfigurability of Modular Pivoting Robots”, in Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021), edited by Kevin Buchin and Éric Colin de Verdière, LIPIcs, 2021, 10:1–10:20.
We give both efficient algorithms and hardness results for reconfiguring
between two connected configurations of modules in the hexagonal grid. The
reconfiguration moves that we consider are “pivots”, where a
hexagonal module rotates around a vertex shared with another module.
Following prior work on modular robots, we define two natural sets of hexagon
pivoting moves of increasing power: restricted and monkey moves. When we
allow both moves, we present the first universal reconfiguration algorithm,
which transforms between any two connected configurations using
O(n3) monkey moves. This result strongly contrasts
the analogous problem for squares, where there are rigid examples that do not
have a single pivoting move preserving connectivity. On the other hand, if we
only allow restricted moves, we prove that the reconfiguration problem becomes
PSPACE-complete. Moreover, we show that, in contrast to hexagons, the
reconfiguration problem for pivoting squares is PSPACE-complete regardless of
the set of pivoting moves allowed. In the process, we strengthen the reduction
framework of Demaine et al. [FUN'18] that we consider of independent
- This paper is also available from LIPIcs.
- The paper is 20 pages.
- The paper is available in PDF (1264k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by