Name
Abstract | ||
|---|---|---|
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(n^3)$ 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 interest. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.SoCG.2021.10 | SoCG |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 10 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hugo A. Akitaya | 1 | 11 | 9.76 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Andrei Gonczi | 3 | 0 | 0.34 |
| Dylan H. Hendrickson | 4 | 0 | 0.34 |
| Adam Hesterberg | 5 | 4 | 7.07 |
| Matias Korman | 6 | 178 | 37.28 |
| Oliver Korten | 7 | 0 | 1.35 |
| Jayson Lynch | 8 | 0 | 2.70 |
| Irene Parada | 9 | 0 | 2.03 |
| Vera Sacristan | 10 | 95 | 11.80 |