TU Eindhoven, The
Netherlandsi.kostitsyna@tue.nlhttps://orcid.org/0000-0003-0544-2257 Utrecht
University, The Netherlands and TU Eindhoven, The
Netherlandst.a.e.ophelders@uu.nlhttps://orcid.org/0000-0002-9570-024X
Universitat Politècnica de Catalunya,
Spainirene.parada@upc.eduhttps://orcid.org/0000-0003-2401-8670 TU Eindhoven,
The Netherlandst.peters1@tue.nlhttps://orcid.org/0000-0002-2702-7532 TU
Eindhoven, The
Netherlandsw.m.sonke@tue.nlhttps://orcid.org/0000-0001-9553-7385 TU Eindhoven,
The Netherlandsb.speckmann@tue.nlhttps://orcid.org/0000-0002-8514-7858 Irina
Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina
Speckmann [100]Theory of computation Computational geometry

# Optimal In-Place Compaction of Sliding Cubes

Irina Kostitsyna  Tim Ophelders  Irene Parada  Tom Peters  Willem Sonke
Bettina Speckmann

###### Abstract

The sliding cubes model is a well-established theoretical framework that
supports the analysis of reconfiguration algorithms for modular robots
consisting of face-connected cubes. The best algorithm currently known for the
reconfiguration problem, by Abel and Kominers [arXiv, 2011], uses $O(n^{3})$
moves to transform any $n$-cube configuration into any other $n$-cube
configuration. As is common in the literature, this algorithm reconfigures the
input into an intermediate canonical shape. In this paper we present an in-
place algorithm that reconfigures any $n$-cube configuration into a compact
canonical shape using a number of moves proportional to the sum of coordinates
of the input cubes. This result is asymptotically optimal. Furthermore, our
algorithm directly extends to dimensions higher than three.

###### keywords:

Sliding cubes, Reconfiguration algorithm, Modular robots

##  1 Introduction

Modular robots consist of a large number of comparatively simple robotic
units. These units can attach and detach to and from each other, move relative
to each other, and in this way form different shapes or configurations. This
shape-shifting ability allows modular robots to robustly adapt to previously
unknown environments and tasks. One of the major questions regarding modular
robots is _universal reconfiguration_ : is there a sequence of moves which
transforms any two given configurations into each other, and if so, how many
moves are necessary? There are a variety of real-world mechatronics or
theoretical computational models for modular robots and the answer to the
universal reconfiguration question differs substantially between systems [3].

In this paper, we study the _sliding cube model_ , which is a well-established
theoretical framework that supports the analysis of reconfiguration algorithms
for modular robots consisting of face-connected cubes. In this model, a module
(cube) can perform two types of moves: straight-line moves called _slides_ and
moves around a corner called _convex transitions_ (see Figure 1). During a
move, the configuration (excluding the moving cube) must stay connected.
Furthermore, there have to be sufficient empty cells in the corresponding grid
to perform the move (see again Figure 1: the cells indicated with red wire
frames must be empty for the move to be possible). Maintaining connectivity
during a sequence of moves is the main challenge when developing algorithms in
the sliding cube model. This connectivity is crucial for most actual modular
robotic systems since it allows them to retain their structure, communicate,
and share other resources such as energy.

Figure 1: Moves in the sliding cube model: slide (a) and convex transition
(b). Solid cubes are part of the configuration, wire frames indicate grid
cells that must be empty.

Almost 20 years ago, Dumitrescu and Pach [8] showed that the sliding cube
model in 2D (or _sliding square model_) is universally reconfigurable. More
precisely, they presented an algorithm that transforms any two given
configurations with $n$ squares into each other in $O(n^{2})$ moves. This
algorithm transforms any given configuration into a canonical horizontal line
and then reverts the procedure to reach the final configuration. It was
afterwards adapted to be _in-place_ using flooded bounding boxes as canonical
intermediate configurations [15]. Recently, Akitaya et al. [4] presented
Gather&Compact: an input-sensitive in-place algorithm which uses $O(Pn)$
moves, where $P$ is the maximum among the perimeters of the bounding boxes of
the initial and final configurations. The authors also show that minimizing
the number of moves required to reconfigure is NP-hard.

These algorithms in 2D do not directly transfer to 3D: they fundamentally rely
on the fact that a connected cycle of squares encloses a well-defined part of
the configuration. One could ask whether the fact that enclosing space in 3D
is more difficult has positive or negative impact on universal reconfiguration
in 3D. Miltzow et al. [14] showed that a direct path to reconfiguration in 3D
is blocked: there exist 3D configurations in which no module on the external
boundary is able to move without disconnecting the configuration. Hence,
simple reconfiguration strategies [11, 13] can generally not guarantee
reconfiguration for all instances. The best algorithm currently known for the
reconfiguration problem in 3D, by Abel and Kominers [1], uses $O(n^{3})$ moves
to transform any $n$-cube configuration into any other $n$-cube configuration,
which is worst-case optimal. As is common in the literature, this algorithm
reconfigures the input into an intermediate canonical shape. The question
hence arises, if—just as in 2D—there is an input-sensitive reconfiguration
algorithm in 3D.

### Results.

In this paper we answer this question in the affirmative: We present an in-
place algorithm that reconfigures any $n$-cube configuration into a compact
canonical shape using a number of moves proportional to the sum of coordinates
of the input cubes. This result is asymptotically optimal. Furthermore, our
algorithm directly extends to hypercube reconfiguration in dimensions higher
than three.

### Additional related work.

For more restricted sliding models, for example, only allowing one of the two
moves in the sliding cube model, reconfiguration is not always possible.
Michail et al. [13] explore universal reconfiguration using _helpers_ or
_seeds_ (dedicated cubes that help other cubes move). They show that the
problem of deciding how many seeds are needed is in PSPACE.

Another popular model for modular robots is the pivoting cube model, in which
the modules move by rotating around an edge shared with a neighboring module.
In this model the extra free-space requirements for the moves that come from
pivoting instead of sliding mean that there are configurations in which no
move is possible. Akitaya et al. [3] show that the reconfiguration problem in
this setting is PSPACE-complete. In contrast, adding five additional modules
to the outer boundary guarantees universal reconfigurability in 2D using
$O(n^{2})$ moves [2]. Other algorithms for pivoting modules require the
absence of narrow corridors in both the initial and final configurations [10,
17]. A more powerful move is to allow the modules to _tunnel_ through the
configuration. With it, $O(n)$ parallel steps suffice to reconfigure 2D and 3D
cubes [5, 6, 12]. However, for most real-world prototype systems, tunnelling
requires the use of _metamodules_ [16] which are sets of modules which act as
a single unit with enhanced capabilities, increasing the granularity of the
configurations.

We require that the configuration stays connected at all times. In a slightly
different model that relaxes the connectivity requirement (referred to as the
_backbone property_), Fekete et al. [9] show that scaled configurations of
labeled squares can be efficiently reconfigured using parallel coordinated
moves with a schedule that is a constant factor away from optimal.

##  2 Preliminaries

In this paper, we study cubical robots moving in the 3-dimensional grid. The
handedness of the coordinate system does not have any impact on the
correctness of our algorithm; in our figures we use a right-handed coordinate
system with $z$ pointing up.

A _configuration_ $\mathcal{C}$ is a subset of coordinates in the grid. The
elements of $\mathcal{C}$ are called _cubes_. We call two cubes _adjacent_ if
they lie at unit distance. For a configuration $\mathcal{C}$, denote by
$G_{\mathcal{C}}$ the graph with vertex set $\mathcal{C}$, whose edges connect
all adjacent cubes. We say a _cell_ is a vertex of $G_{\mathbb{Z}^{3}}$, which
is not occupied by a cube in $\mathcal{C}$. We always require a configuration
to remain _connected_ , that is, $G_{\mathcal{C}}$ must be connected. For ease
of exposition we assume $\mathcal{C}$ consists of at least two cubes. We call
a configuration $\mathcal{C}$ _nonnegative_ if
$\mathcal{C}\subseteq\mathbb{N}^{3}$.

In the sliding cubes model, a configuration can rearrange itself by letting
cubes perform moves. A move is an operation that replaces a single cube
$c\in\mathcal{C}$ by another cube $c^{\prime}\notin\mathcal{C}$. Moves come in
two types: _slides_ and _convex transitions_ , see Figure 1. In both cases, we
consider a 4-cycle $\gamma$ in $G_{\mathbb{Z}^{3}}$. For slides, three cubes
of $\gamma$ are in $\mathcal{C}$; $c^{\prime}$ is the cube of $\gamma$ not in
$\mathcal{C}$, and $c$ is adjacent to $c^{\prime}$. For convex transitions,
$\gamma$ has exactly two adjacent cubes in $\mathcal{C}$; $c$ is one of these
two cubes, and $c^{\prime}$ is the vertex of $\gamma$ not adjacent to $c$. The
slide or convex transition is a _move_ if and only if
$\mathcal{C}\setminus\\{c\\}$ is connected.

Let $\mathcal{C}$ be a nonnegative configuration. Call a cube $c=(x,y,z)$
_finished_ if the cuboid spanned by the origin and $c$ is completely in
$\mathcal{C}$, that is, if
$\\{0,\ldots,x\\}\times\\{0,\ldots,y\\}\times\\{0,\ldots,z\\}\subseteq\mathcal{C}$.
We call $\mathcal{C}$ _finished_ if all cubes in $\mathcal{C}$ are finished.
The _compaction problem_ starts with an arbitrary connected configuration
$\mathcal{C}$ and finishes when all cubes are finished.

Most of the algorithm works on vertical contiguous strips of cubes in
$\mathcal{C}$ called subpillars. More precisely, a _subpillar_ is a subset of
$\mathcal{C}$ of the form
$\\{x\\}\times\\{y\\}\times\\{z_{b},\ldots,z_{t}\\}$. In the remainder of this
paper, we denote this subpillar by $\langle x,y,z_{b}\,..\,z_{t}\rangle$. The
cube $(x,y,z_{t})$ is called the _head_ , and the remainder $\langle
x,y,z_{b}\,..\,z_{t}-1\rangle$ is called the _support_. A _pillar_ is a
maximal subpillar, that is, a subpillar that is not contained in any other
subpillar. Note that there can be multiple pillars with the same $x$\- and
$y$\- coordinate above each other, as long as there is a gap between them. Two
sets $S$ and $S^{\prime}$ of cubes are _adjacent_ if $S$ contains a cube
adjacent to a cube in $S^{\prime}$. The _pillar graph_ $\mathcal{P}_{S}$ of a
set $S$ of cubes is the graph whose vertices are the pillars of $S$ and whose
edges connect adjacent pillars.

##  3 Algorithm

For a set of cubes $S\subseteq\mathcal{C}$, denote its _coordinate vector sum_
by $(X_{S},Y_{S},Z_{S})=\sum_{(x,y,z)\in S}(x,y,z)$. Let $\mathcal{C}_{>0}$ be
the subset of cubes $(x,y,z)\in\mathcal{C}$ for which $z>0$, and
$\mathcal{C}_{0}$ be the subset of cubes for which $z=0$. Let the _potential_
of a cube $c=(c_{x},c_{y},c_{z})$ be $\Pi_{c}=w_{c}(c_{x}+2c_{y}+4c_{z})$,
where the _weight_ $w_{c}$ depends on the coordinates of $c$ in the following
way. If $c_{z}>1$, then $w_{c}=5$, if $c_{z}=1$, then $w_{c}=4$. If $c_{z}=0$,
then $w_{c}$ depends on $c_{y}$. If $c_{y}>1$, then $w_{c}=3$, if $c_{y}=1$,
then $w_{c}=2$ and lastly, if both $c_{z}=c_{y}=0$, then $w_{c}=1$. We aim to
minimize the _potential function_
$\Pi_{\mathcal{C}}=\sum_{c\in\mathcal{C}}\Pi_{c}$. From now on, let
$\mathcal{C}$ be an unfinished nonnegative configuration. We call a sequence
of $m$ moves _safe_ if the result is a nonnegative instance
$\mathcal{C}^{\prime}$, such that
$\Pi_{\mathcal{C}^{\prime}}<\Pi_{\mathcal{C}}$ and
$m=O(\Pi_{\mathcal{C}}-\Pi_{\mathcal{C}^{\prime}})$. This means that the
sequence of moves reduces the potential by at least $m$ by going from
$\mathcal{C}$ to $\mathcal{C}^{\prime}$. We show that if $\mathcal{C}$ is
unfinished, it always admits a safe move sequence.

The main idea is as follows. For a configuration $\mathcal{C}$, whenever
possible, we try to reduce $Z_{\mathcal{C}}$. If that is not possible, then
the configuration must admit another type of move, where a complete pillar is
moved to a different $x$\- and $y$-coordinate. In this way, by reducing either
the $z$-coordinate of cubes, or the $x$\- or $y$-coordinate, we guarantee that
eventually every cube becomes finished.

### Local Z reduction.

Let $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be a subpillar of $\mathcal{C}$.
We refer to the four coordinates $\\{(x-1,y),(x+1,y),(x,y-1),(x,y+1)\\}$ as
the _sides_ of $P$. On each side, $P$ may have one or more adjacent pillars.
We order these by their $z$-coordinates; as such, we may refer to the top- or
bottommost adjacent pillar on a side of $P$. We say that a set of cubes
$S\subseteq\mathcal{C}$ is _non-cut_ if $G_{\mathcal{C}\setminus S}$ is
connected or empty. A pillar of $\mathcal{C}$ is non-cut if and only if it is
a non-cut vertex of the pillar graph $\mathcal{P}_{\mathcal{C}}$.

Let $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be a non-cut subpillar, and let
$P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$ be a pillar
adjacent to $P$. We define a set of operations of at most three moves within
$P$ which locally reduce $Z_{\mathcal{C}}$ (see Figure 2). Because $P$ is non-
cut, $\mathcal{C}\setminus P$ is connected. Therefore, if for each of these
operations cubes of $P$ move in such a way that each component (of cubes
originating from $P$) remains adjacent to a cube of $\mathcal{C}\setminus P$,
then the result is a valid configuration.

Figure 2: Examples of operations (3–3); hatched cubes are non-cut and dashed
outlines indicate cells that must be empty. Each case admits a move sequence
that reduces $Z_{\mathcal{C}}$.

If $P^{\prime}$ is a topmost adjacent pillar of $P$ and $z^{\prime}_{t}\leq
z_{t}-2$, then the topmost cube of $P$ admits a convex transition that
decreases $Z_{\mathcal{C}}$.

If $z^{\prime}_{b}>z_{b}$ and $(x,y,z^{\prime}_{b}-1)$ is not a cut cube
(i.e., $\langle x,y,z_{b}\,..\,z^{\prime}_{b}-2\rangle$ has an adjacent cube
in $\mathcal{C}$, or $z^{\prime}_{b}=z_{b}+1$), then there is a move sequence
that decreases $Z_{\mathcal{C}}$: first slide $(x,y,z^{\prime}_{b}-1)$ to
$(x^{\prime},y^{\prime},z^{\prime}_{b}-1)$ and then slide
$(x,y,z^{\prime}_{b})$ to $(x,y,z^{\prime}_{b}-1)$. There is one special case.
We say that $P$ is _locked_ if the head of $P$ has no adjacent cubes except
for $P$’s support. If $P$ is locked and $z^{\prime}_{b}=z_{t}-1$, then the
second slide would disconnect $P$’s head from the rest of the configuration.
To avoid this, before performing the second slide, we _unlock_ $P$ by sliding
the head of $P$ from $(x,y,z_{t})$ to $(x^{\prime},y^{\prime},z_{t})$, as
shown in the right part of Figure 2b.

If $(x,y,z_{b}-1)\notin\mathcal{C}$ and $z^{\prime}_{b}<z_{b}$, then (after
unlocking $P$, if necessary) $(x,y,z_{b})$ admits a slide to $(x,y,z_{b}-1)$
that decreases $Z_{\mathcal{C}}$.

If $(x,y,z_{b}-1)\notin\mathcal{C}$, $P^{\prime}$ is a bottommost adjacent
pillar of $P$, and $z_{b}=z^{\prime}_{b}>0$, then (after unlocking $P$, if
necessary) $(x,y,z_{b})$ admits a convex transition to
$(x^{\prime},y^{\prime},z^{\prime}_{b}-1)$ that decreases $Z_{\mathcal{C}}$.

######  Lemma 3.1.

Let $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be a non-cut pillar. If (a–d) do
not apply to $P$, then on each side, $P$ has at most one adjacent pillar
$P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$. For these
pillars $P^{\prime}$, we have $z_{t}\leq z^{\prime}_{t}+1$, and either
$z_{b}<z^{\prime}_{b}$ or $z_{b}=z^{\prime}_{b}=0$.

######  Proof 3.2.

Consider one side $s$ of $P$. Because (a) does not apply to $P$, for any
adjacent pillar $P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$, we know that
$z_{t}\leq z^{\prime}_{t}+1$. Assume that $(x,y,z^{\prime}_{b}-1)$ is not a
cut cube. Because (b) does not apply, $z_{b}\geq z^{\prime}_{b}$, and because
(c) does not apply either, $z_{b}=z^{\prime}_{b}$, and finally because (d)
does not apply, we have $z_{b}=z^{\prime}_{b}=0$. Now assume that
$(x,y,z^{\prime}_{b}-1)$ is a cut cube. Then because (c) does not apply, we
have $z_{b}\leq z^{\prime}_{b}$, and finally because (d) does not apply, we
have $z_{b}<z^{\prime}_{b}$ or $z_{b}=z^{\prime}_{b}=0$. If
$z_{b}=z^{\prime}_{b}=0$ for each adjacent pillar $P^{\prime}$, then each side
of $P$ can have at most one pillar. If $z_{b}<z^{\prime}_{b}$, then, because
(b) does not apply, $(x,y,z^{\prime}_{b}-1)$ is a cut cube. Therefore, also in
this case, there can be no cube adjacent to the subpillar $\langle
x,y,z_{b}\,..\,z^{\prime}_{b}-2\rangle$, and therefore also in this case there
can be at most one adjacent pillar on each side.

### Pillar shoves.

Next, we consider longer move sequences that still involve a single subpillar.
A central operation of our algorithm is a _pillar shove_ , which takes as
parameters a subpillar $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ and a side
$(x^{\prime},y^{\prime})$ of $P$. The result of the pillar shove is the set of
cubes

$\mathrm{shove}(\mathcal{C},P,(x^{\prime},y^{\prime}))\ :=\
(\mathcal{C}\setminus P)\ \cup\ \langle
x^{\prime},y^{\prime},z_{b}\,..\,z_{t}-1\rangle\ \cup\
\\{(x,y,z_{b})\\}\text{,}$

in which the support is effectively shifted to the side
$(x^{\prime},y^{\prime})$, and the head is effectively moved from
$(x,y,z_{t})$ to $(x,y,z_{b})$. Although $\mathrm{shove}(\mathcal{C},\langle
x,y,z_{b}\,..\,z_{t}\rangle,(x^{\prime},y^{\prime}))$ is well-defined, it is
not necessarily a connected configuration, let alone safely reachable from
$\mathcal{C}$.

Figure 3: Example of pillar shoves for a long pillar (3) and a short pillar
(3′).

Let $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be a non-cut subpillar, and assume
that on at least two sides $(x^{\prime},y^{\prime})$ and
$(x^{\prime\prime},y^{\prime\prime})$ of $P$, no cube except possibly the head
$(x,y,z_{t})$ has an adjacent cube. Moreover, assume that
$(x^{\prime},y^{\prime},z_{t})\in\mathcal{C}$. Then the pillar shove can be
done without without collisions and while keeping connectivity, as illustrated
in Figure 3. There are two cases: one where $P$ has at least $9$ cubes, in
which case we take $O(|P|)$ moves (illustrated on the left side of Figure 3).
The case where $P$ has fewer than $9$ cubes takes $O(1)$ moves and does not
require the existence of the second side $(x^{\prime\prime},y^{\prime\prime})$
(illustrated on the right side of Figure 3). A pillar shove reduces
$Z_{\mathcal{C}}$ by $z_{t}-z_{b}$ and takes $O(z_{t}-z_{b})$ moves, so it is
safe.

Assume that $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ has at most one adjacent
pillar on each side, and there exists an adjacent pillar $P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$ with
$z^{\prime}_{b}>z_{b}$ (assume that $P^{\prime}$ is such a pillar with the
lowest $z^{\prime}_{b}$), and there is a side
$(x^{\prime\prime},y^{\prime\prime})\neq(x^{\prime},y^{\prime})$ of $P$ such
that $(x^{\prime\prime},y^{\prime\prime},z_{b})\notin\mathcal{C}$. Together,
these assumptions imply that both sides $(x^{\prime\prime},y^{\prime\prime})$
and $(x^{\prime},y^{\prime})$ are empty up to at least $z^{\prime}_{b}-1$.
Then the subpillar $\langle x,y,z_{b}\,..\,z^{\prime}_{b}\rangle$ (after
unlocking $P$, if necessary) admits a pillar shove.

######  Lemma 3.3.

Let $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be a non-cut subpillar. If (3–3)
do not apply to $P$, then $P$ has no adjacent pillar $\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$ with
$z^{\prime}_{b}>z_{b}$.

######  Proof 3.4.

Assume that $P$ has at least two adjacent pillars, say $P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$ and
$P^{\prime\prime}=\langle
x^{\prime\prime},y^{\prime\prime},z^{\prime\prime}_{b}\,..\,z^{\prime\prime}_{t}\rangle$,
such that $z_{b}<z^{\prime}_{b}$ and $z_{b}<z^{\prime\prime}_{b}$; let
$P^{\prime}$ denote the lowest one, such that $z_{b}<z^{\prime}_{b}\leq
z^{\prime\prime}_{b}$. Then
$(x^{\prime\prime},y^{\prime\prime},z_{b})\notin\mathcal{C}$, which
contradicts that (3) does not apply. Therefore, there can be at most one such
pillar. However, this, together with Lemma 3.1, implies that on all other
sides $(x^{\prime\prime},y^{\prime\prime})\neq(x^{\prime},y^{\prime})$,
$(x^{\prime\prime},y^{\prime\prime},z_{b})\in\mathcal{C}$. This means that
$(x,y,z^{\prime}_{b}-1)$ is not a cut-cube, contradicting that (3) does not
apply. Therefore, there can be no such adjacent pillars.

In summary, if (3–3) do not apply to any non-cut subpillar, then for any non-
cut pillar $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ and any adjacent pillar
$\langle x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$, we
have $z^{\prime}_{b}=z_{b}=0$.

### Local potential reduction.

We may greedily reduce the potential by moving individual cubes with $z>0$.

Perform any move of $\mathcal{C}$ that moves a cube of $\mathcal{C}_{>0}$,
reduces the potential, and results in a nonnegative instance.

######  Lemma 3.5.

If an unfinished configuration $\mathcal{C}$ does not admit any move of type
(3), and $\langle x,y,z_{b}\,..\,z_{t}\rangle$ is a component of
$\mathcal{C}_{>0}$ that consists of a single pillar, then $P=\\{(0,0,1)\\}$
and $(0,0,0)\in\mathcal{C}$.

######  Proof 3.6.

Because $\mathcal{C}_{>0}$ does not contain cubes with $z=0$, we have
$z_{b}=1$ or $z_{b}>1$. If $z_{b}>1$, then $\mathcal{C}$ would be not
connected, so this cannot happen. Likewise, if $z_{b}=1$ and
$(x,y,0)\notin\mathcal{C}$ makes $\mathcal{C}$ disconnected, so this cannot
happen either. Therefore $z_{b}=1$ and $(x,y,0)\in\mathcal{C}$. If $z_{t}>1$,
then the topmost cube of $P$ can do a convex transition to $(x+1,y,z_{t}-1)$,
reducing the potential. Therefore $z_{t}=1$ and $P=\\{(x,y,1)\\}$. If $x>0$ or
$y>0$, then we can move the single cube of $P$: using the cube at $(x,y,0)$,
the cube of $P$ can slide or convex transition closer to the origin $(0,0,0)$.
Therefore, $z_{b}=z_{t}=1$ and $x=y=0$.

######  Corollary 3.7.

If a nontrivial instance $\mathcal{C}$ does not admit any move of type (3)
then $\mathcal{C}_{>0}$ has at most one component that consists of a single
pillar.

### Low and high components.

Suppose that (3–3) do not apply. Let $\mathcal{LH}_{\mathcal{C}}$ be the
bipartite graph obtained from $G_{\mathcal{C}}$ by contracting the components
of $G_{\mathcal{C}_{0}}$ and $G_{\mathcal{C}_{>0}}$ to a single vertex (see
Figure 4). We call $\mathcal{LH}_{\mathcal{C}}$ the _low-high graph_ of
$\mathcal{C}$, and we call the vertices of $\mathcal{LH}_{\mathcal{C}}$ that
correspond to components of $G_{\mathcal{C}_{0}}$ and $G_{\mathcal{C}_{>0}}$
_low_ and _high_ components, respectively.

Figure 4: An example configuration $\mathcal{C}$ and its low-high graph
$\mathcal{LH}_{\mathcal{C}}$.

We will use the following lemma several times.

######  Lemma 3.8.

Let $H$ be a high component and $P$ be a pillar of $H$. For every component
$H^{\prime}$ of $H\setminus P$, there exists a non-cut pillar of $H^{\prime}$
that is also a non-cut pillar of $H$.

######  Proof 3.9.

Any component with at least two pillars contains at least two non-cut pillars
and every component contains at least one non-cut pillar, so let $P^{\prime}$
be an arbitrary non-cut pillar of $H^{\prime}$. $H\setminus P^{\prime}$ has at
most two components, namely $H^{\prime}\setminus P^{\prime}$ and $H\setminus
H^{\prime}$. If $P^{\prime}$ is a non-cut pillar of $H$, the lemma holds.
Else, if $P^{\prime}$ is a cut pillar of $H$, then it has exactly these
components, so $H^{\prime}\setminus P^{\prime}$ is nonempty and $P$ is
adjacent to $P^{\prime}$. Therefore, $H^{\prime}$ consists of multiple pillars
and hence at least two non-cut pillars. Let $P^{\prime\prime}\neq P^{\prime}$
be a second non-cut pillar of $H^{\prime}$. We claim that $P^{\prime\prime}$
is also a non-cut pillar of $H$. Indeed, because $P$ and $P^{\prime}$ are
adjacent, the sets $H^{\prime}\setminus P^{\prime\prime}\supseteq P^{\prime}$
and $H\setminus H^{\prime}\supseteq P$ are adjacent. Hence, $H\setminus
P^{\prime\prime}=(H^{\prime}\setminus P^{\prime\prime})\cup(H\setminus
H^{\prime})$ has a single component, so $P^{\prime\prime}$ is a non-cut pillar
of $H$.

######  Lemma 3.10.

Assume $\mathcal{C}$ does not admit any move of type (3–3). Suppose that $H$
is a high component such that $\mathcal{C}\setminus H$ is connected. Then any
pillar of $H$ is a non-cut subpillar of $\mathcal{C}$.

######  Proof 3.11.

Suppose for a contradiction that a pillar $P$ of $H$ is a cut subpillar of
$\mathcal{C}$. Then $\mathcal{C}\setminus P$ contains at least one component
$H^{\prime}$ that does not intersect $\mathcal{C}\setminus H$. Therefore,
$H^{\prime}$ is also a component of $H\setminus P$, so by Lemma 3.8, there
exists a non-cut pillar $P^{\prime}=\langle
x^{\prime},y^{\prime},z^{\prime}_{b}\,..\,z^{\prime}_{t}\rangle$ of
$H^{\prime}$ that is also a non-cut pillar of $H$. If $z^{\prime}_{b}>1$ or
$(x^{\prime},y^{\prime},0)\notin\mathcal{C}$, then $P^{\prime}$ would be a
non-cut pillar of $\mathcal{C}$. If $\mathcal{C}$ does not admit any move of
type (3–3), all non-cut pillars of $\mathcal{C}$ start at $z=0$, which
contradicts $z^{\prime}_{b}>1$ or
$(x^{\prime},y^{\prime},0)\notin\mathcal{C}$. Therefore, $z^{\prime}_{b}=1$
and $(x^{\prime},y^{\prime},0)\in\mathcal{C}$, but then $H^{\prime}$ would not
be a component of $\mathcal{C}\setminus P$, as $H^{\prime}$ is adjacent to
$(x^{\prime},y^{\prime},0)\in\mathcal{C}\setminus P$. Hence, $H^{\prime}$
cannot exist, completing the proof.

######  Corollary 3.12.

If $H$ is a high component such that $\mathcal{C}\setminus H$ is connected,
then every pillar of $H$ is part of a pillar of $\mathcal{C}$ starting at
$z=0$.

######  Lemma 3.13.

Assume $\mathcal{C}$ does not admit any move of type (3–3). If $H$ is a high
component such that $\mathcal{C}\setminus H$ is connected, then $H$ consists
entirely of finished cubes.

######  Proof 3.14.

Assume for contradiction that $H$ contains an unfinished cube. Because of
Corollary 3.12, every pillar of $H$ is part of a pillar of $\mathcal{C}$
starting at $z=0$. Therefore, $H$ contains an unfinished cube $(x,y,z)$ with
$x>0$ or $y>0$. Let $c$ be such a cube that lexicographically maximizes
$(z,-y,-x)$. If $x>0$ and $(x-1,y,z)\notin H$ (and thus
$(x-1,y,z)\notin\mathcal{C}$), then we can move $c$ to either $(x-1,y,z)$ or
$(x-1,y,z-1)$, reducing the potential while maintaining a nonnegative
instance, so (3) would apply. If $y>0$ and $(x,y-1,z)\notin H$, then we can
similarly move $c$ to either $(x,y-1,z)$ or $(x,y-1,z-1)$. On the other hand,
if both (1) $x=0$ or $(x-1,y,z)\in H$ and (2) $y=0$ or $(x-1,y,z)\in H$, then
because $c$ is the unfinished cube of $H$ that maximizes $(z,-y,-x)$, the
cubes $(x-1,y,z)$ (if $x>0$) and $(x,y-1,z)$ (if $y>0$) are finished, but then
$(x,y,z)$ would also be finished. Contradiction.

######  Corollary 3.15.

Any high component that contains a finished cube also contains $(0,0,1)$.
Hence there is at most one such high component.

### Handling low components.

We will now pick a vertex $R$ of $\mathcal{LH}_{\mathcal{C}}$ that we call the
_root_ of $\mathcal{LH}_{\mathcal{C}}$. If $(0,0,0)\in\mathcal{C}$, pick $R$
to be the low component that contains $(0,0,0)$. Otherwise, pick $R$ to be an
arbitrary low component. Let $d$ be the maximum distance in
$\mathcal{LH}_{\mathcal{C}}$ from $R$ over all vertices of
$\mathcal{LH}_{\mathcal{C}}$. Let $\mathcal{U}$ be the set of vertices of
$\mathcal{LH}_{\mathcal{C}}$ that are locally furthest away (in
$\mathcal{LH}_{\mathcal{C}}$) from $R$. That is, all neighbors $v$ of a vertex
$u\in\mathcal{U}$ lie closer to $R$. All vertices of $\mathcal{U}$ are non-cut
subsets of $\mathcal{C}$. Therefore, if $\mathcal{U}$ contains a high
component $H$, then $H$ consists entirely of finished cubes (and $H$ is
adjacent to $R$), so $\mathcal{U}$ contains at most one high component.

If $d=0$, then $\mathcal{C}$ consists of a single low component. If $d=1$,
then $\mathcal{C}$ consists of one high and one low component. Set
$\mathcal{U}$ contains exactly one high component, and it consists entirely of
finished cubes. We will handle these two cases later. If $d\geq 2$, then
$\mathcal{C}$ consists of at least two low components and $\mathcal{U}$
consists of at least one low component, and at most one high component.

We call a low component $L$ _clear_ if $\mathcal{C}\setminus L$ is connected,
$L\neq R$, and $L$ is connected to a non-cut pillar $P$ in
$\mathcal{C}\setminus L$. We call such a pillar $P$ a _clearing_ pillar. We
show in Lemma 3.16 that if $d\geq 2$, there is at least one clear low
component. For this, consider a low component that is furthest from $R$ (i.e.
at distance $d$), and let $H$ be an adjacent high component. Let
$\mathcal{L}_{H}$ be the set of low components in $\mathcal{U}$ that are
adjacent to $H$ (and hence also lie at distance $d$ from $R$).

######  Lemma 3.16.

At least one low component $L\in\mathcal{L}_{H}$ is connected to $H$ via a
non-cut pillar of $\mathcal{C}\setminus L$.

######  Proof 3.17.

Let $\mathcal{C}^{\prime}=\mathcal{C}\setminus\bigcup_{L\in\mathcal{L}_{H}}L$.
Let $H_{\mathcal{L}_{H}}$ be the set of cubes of $H$ that are adjacent to a
low component in $\mathcal{L}_{H}$. Fix an arbitrary cube $c_{s}$ of $R$, and
in the graph $G_{\mathcal{C}^{\prime}}$, consider a cube $c$ of
$H_{\mathcal{L}_{H}}$ that is farthest from $c_{s}$. Let $P$ be the pillar of
$H$ that contains $c$. We will show that $P$ is a non-cut pillar of
$\mathcal{C}^{\prime}$. Suppose for a contradiction that $P$ is a cut pillar,
then $\mathcal{C}^{\prime}\setminus P$ contains at least two component, only
one of which does not contain $R$. Let $H^{\prime}$ be such a component of
$\mathcal{C}^{\prime}\setminus P$ not containing $R$. If $H^{\prime}$ contains
a cube not in $H$, then that cube lies in a low or high component of
$\mathcal{C}^{\prime}$ that lies closer to $R$, which therefore remains
connected to $R$ after removing $P$. Therefore, $H^{\prime}$ is a subset of
$H$. All cubes $(x,y,z)\in H^{\prime}$ with $z=1$ lie farther from $c_{s}$
than $c$, and therefore $H^{\prime}$ does not contain any cubes of
$H_{\mathcal{L}_{H}}$, so $H^{\prime}$ is not adjacent to any cubes of
$\mathcal{L}_{H}$. Therefore, $H^{\prime}$ is not adjacent to any cubes of
$(\mathcal{C}\setminus P)\setminus H^{\prime}$. By Lemma 3.8, $H^{\prime}$
contains at least one non-cut pillar $P^{\prime}$ that is also a non-cut
pillar of $H$. $P^{\prime}$ is also a non-cut pillar of $\mathcal{C}$, but all
non-cut pillars of $\mathcal{C}$ start at $z=0$ (Corollary 3.12), which is a
contradiction.

We will now present an algorithm that repeatedly selects a (non-root) clear
low component $L$, and performs the following move on it:

Perform any move of $\mathcal{C}$ that moves a cube of $L$, reduces the
potential, and results in a nonnegative instance. Same as (3), but now on a
low component.

Moves of type (3.17) serve any of three purposes:

  1. (1)

The component connects to a different low component, merging them.

  2. (2)

The component connects to the root, and becomes part of the root.

  3. (3)

The component reaches the origin (at which point it becomes the root).

In between these operations, we exhaustively perform potential reductions to
high components using move types (3–3). If none of the moves (3–3.17) are
available, then this means that $L$ does not have enough cubes to reach the
origin.

In this case, we want to move the clearing pillar and do a pillar shove.
However, it could be that there are cubes around the clearing pillar, or that
the clearing pillar would disconnect the low component. Let $N$ be the set of
grid cells $c$ neighboring $P$ with $z=1$, such that $c$ lies within the
bounding box of $\mathcal{C}$.

######  Lemma 3.18.

Let $\mathcal{C}$ be a configuration that does not admit moves of type
(3–3.17). Let $L$ be a clear component and $P=\langle
x,y,z_{b}\,..\,z_{t}\rangle$ be its clearing pillar. The cubes in $N$ need to
be either all present, or all absent from $\mathcal{C}$.

######  Proof 3.19.

Assume for contradiction that at least one, but at most three of the cubes
neighboring $P$ with $z=1$ are present. Let these cubes be $c_{1}$, $c_{2}$,
and $c_{3}$, not all need to be present. Since $P$ is a clearing pillar,
$(\mathcal{C}\setminus L)\setminus P$ is connected. Therefore, the cube
$(x,y,2)$ can do a potential reducing move of type (3), which is a
contradiction.

Let $L$ be a clear component and $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be
its clearing pillar. Assume that all cubes in $N$ be present. By definition,
$L\neq R$. Therefore, there exists an empty spot $e$, with coordinates
$(e_{x},e_{y},0)$, with $e_{x}<x$ or $e_{y}<y$. Let $e$ be such an empty spot
with highest $y$, and from those, the one with highest $x$. We now take the
cube $(x,y,0)$ and move it on a shortest path via $z=-1$ towards $e$, reducing
its potential. Because all cubes in $N$ are present, and because those cubes
are part of $\mathcal{C}\setminus L$, of which $P$ is a non-cut pillar, the
configuration stays connected during this move.

If (3–3.19) do not apply, then all cubes from $N$ are not in $\mathcal{C}$ by
Lemma 3.18.

Let $L$ be a clear component and $P=\langle x,y,z_{b}\,..\,z_{t}\rangle$ be
its clearing pillar. All cubes in $N$ are absent from $\mathcal{C}$. Gather
cubes from $L$ towards $P$ according to Figure 5 and do a pillar shove on $P$.
Then, move the extra cubes back to their original location.

The only reason that (3) is not possible, is because $P$ is a cut pillar,
since it is the only pillar connecting $L$ to the other components. Therefore,
gathering cubes from $L$ to $P$ makes this pillar shove viable.

This is done in the following way. Let the clearing pillar of $L$ be
$P=\langle x,y,z_{b}\,..\,z_{t}\rangle$. Note that because (3–3.19) do not
apply, $z_{b}=1$. Let $z_{t}$ be the highest $z$ such that only $(x,y,z_{t})$
has a horizontal neighboring cube $(x^{\prime},y^{\prime},z_{t})$. Let
$(x^{\prime},y^{\prime})$ be the side of $P$ that is lexicographically
smallest. This is the direction in which we would like to do a pillar shove.
Let $c=(x,y,0)\in L$ be the cube below $P$. Assume that $P$ has at least size
$4$. Then, repeatedly select the non-cut cube $c\in L$ that lexicographically
maximizes $(z,y,x)$ and move it towards $P$ to create the configuration
visible in Figure 5. Now $P$ can execute a pillar shove in the direction of
$(x^{\prime},y^{\prime})$. If $P$ has less than $4$ cubes we gather cubes
towards $P$ as in Figure 6. Then, using a constant number of moves, we can
decrease the potential vector, while maintaining connectivity.

Figure 5: The start configuration for a pillar shove for a clearing pillar of
height at least $4$. The blue cubes are required and need to be gathered. The
red cube is part of $L$. Figure 6: The start configuration for a pillar shove
for a small (size less than 4) clearing pillar. The blue cubes are required to
keep $L$ connected to the clearing pillar and will need to be gathered if they
are not present yet. The red cubes can be part of $L$. Left: Blue cubes
necessary for a clearing pillar of height $2$ or $3$. Right: configuration
necessary for a clearing pillar of height $1$.

This algorithm terminates when no clear low component (and hence only the root
low component) remains. We are left with two cases: Either no high component
remains ($d=0$), or there is at most one high component ($d=1$), which
consists of entirely finished cubes.

All of the moves (3–3.19) not only work in $3$ dimensions, they also work in
$2$ dimensions when instead of prioritizing reducing the $z$-coordinate, we
prioritize reducing the $y$-coordinate. Moreover, these moves never move the
origin. Therefore, we can now run the exact same moves on the bottom layer in
2D, until the root component is finished. If there is still a high component,
it stays connected via the origin. We end up with a finished configuration.

### Running time.

Recall that the _potential_ of a cube $c=(c_{x},c_{y},c_{z})$ is
$\Pi_{c}=w_{c}(c_{x}+2c_{y}+4c_{z})$, where the _weight_ $w_{c}$ depends on
the coordinates of $c$ in the following way. If $c_{z}>1$, then $w_{c}=5$, if
$c_{z}=1$, then $w_{c}=4$. If $c_{z}=0$, then $w_{c}$ depends on $c_{y}$. If
$c_{y}>1$, then $w_{c}=3$, if $c_{y}=1$, then $w_{c}=2$ and lastly, if both
$c_{z}=c_{y}=0$, then $w_{c}=1$. The potential of the complete configuration
is the sum of potential of the individual cubes. Moreover, a sequence of $m$
moves is _safe_ if the result is a nonnegative instance
$\mathcal{C}^{\prime}$, such that
$\Pi_{\mathcal{C}^{\prime}}<\Pi_{\mathcal{C}}$ and
$m=O(\Pi_{\mathcal{C}}-\Pi_{\mathcal{C}^{\prime}})$. Each move of type
(3–3.19) strictly reduces the potential function. Moreover, each of the moves
(3–3.19) is safe. We show the same for operations of type (3.19):

######  Lemma 3.20.

Operations of type (3.19) are safe.

######  Proof 3.21.

We will show that any operation of type (3.19) strictly decreases
$P_{\mathcal{C}}$ by $O(x)$ and uses $O(x)$ moves to do so. First analyse the
operations of type (3.19) with a pillar of size larger than one, the head
$c=(c_{x},c_{y},c_{z})$ of the pillar involved moves down from its own
$z$-coordinate to $z=1$, so $P_{\mathcal{C}}$ reduces by $4(c_{z}-1)$. The
cubes beneath $c$ from $z=1$ up to $c_{z}$ might increase their $x$\- or
$y$-coordinate by $1$. Therefore, the potential also increases by $2(c_{z}-1)$
at most. The cubes that are gathered and then returned do not move positions
and therefore do not affect the potential. Moreover, $w_{c}$ for the head
becomes one lower, because $c_{z}$ decreases from $c_{z}>1$ to $c_{z}=1$. In
total, the potential $P_{\mathcal{C}}$ decreases by $2(c_{z}-1)+c_{x}+c_{y}$.
For operations of this type with a pillar of size one, the potential decreases
by $c_{z}+c_{x}+c_{y}$, since the head moves from $z=1$ to $z=0$.

Now we will show that executing one of these operations, which reduces
$\Pi_{\mathcal{C}}$ by $O(c_{z}+c_{x}+c_{y})$ takes $O(c_{z}+c_{x}+c_{y})$
moves and is therefore safe. Moving via a shortest path over a component with
$x$ cubes takes $O(x)$ moves. Gathering the seven cubes from $L$ to the
clearing pillar and moving them back takes at most $O(c_{x}+c_{y})$ moves,
since $L$ cannot reach the origin and has therefore size at most
$O(c_{x}+c_{y})$. Then, the normal pillar shove takes $O(c_{z})$ moves. Thus,
the total operation takes $O(c_{z}+c_{x}+c_{y})$ moves and is therefore safe.

Because all operations are safe and reduce the potential, the algorithm
performs at most
$O(\Pi_{\mathcal{C}})=O(X_{\mathcal{C}}+Y_{\mathcal{C}}+Z_{\mathcal{C}})$
moves. For the problem of reconfiguring the cubes into a finished
configuration, this is worst-case optimal. An example achieving this bound is
a configuration consisting of a path of cubes in a bounding box of equal side
lengths $w$ tracing from the origin to the opposite corner of the bounding
box. To see that, note that any finished cube at position $(x,y,z)$ requires
there to exist $n\geq xyz$ cubes, so at least one of $x$, $y$, and $z$ is at
most $n^{1/d}$ for any candidate finished position. There are $\Omega(n)$
cubes $(x^{\prime},y^{\prime},z^{\prime})$ that are initially
$\Omega(w-n^{1/3})=\Theta(n)=\Theta(x^{\prime}+y^{\prime}+z^{\prime})$ away
from any such potential finished position.

##  4 Conclusion

We presented an in-place algorithm that reconfigures any configuration of
cubes into a compact canonical shape using a number of moves that is
proportional to the sum of coordinates of the input cubes. This result is
asymptotically optimal. However, just as many other algorithms in the
literature, our bounds are amortized in the sense that we make use of a number
of dedicated cubes which help other cubes move by establishing the necessary
connectivity in their neighborhood. This is in particular the case with our
pillar shoves, that need some additional cubes to gather at the pillar, to
then move up and down the pillar to facilitate moves. These extra moves are
charged to one cube in the pillar reducing its coordinates. In the literature
such cubes are referred to as _helpers_ , _seeds_ , or even _musketeers_ [2,
7, 13].

Such helping cubes are in many ways in conflict with the spirit of modular
robot reconfiguration: ideally each module should be able to run the same
program more or less independently, without some central control system
sending helpers to those places where they are needed. The input-sensitive
Gather&Compact algorithm in 2D by Akitaya et al. [4] does not require
amortized analysis and gives a bound on the number of moves for each square in
terms of the perimeters of the input and output configurations. The question
hence arises whether it is possible to arrive at sum-of-coordinates bounds
either in 2D or 3D without amortization? For example, is there a compaction
algorithm in which each cube in the configuration that starts at position
$(x,y,z)$ performs at most $O(x+y+z+a)$ moves, where $a$ is the average
$L_{1}$-distance that cubes lie from the origin?

## References

  * [1] Zachary Abel and Scott Duke Kominers.  Universal reconfiguration of (hyper-)cubic robots.  ArXiv e-Prints, 2011.  URL: https://arxiv.org/abs/0802.3414v3.
  * [2] Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, and Vera Sacristán.  Universal reconfiguration of facet-connected modular robots by pivots: The O(1) musketeers.  Algorithmica, 83(5):1316–1351, 2021.  doi:10.1007/S00453-020-00784-6.
  * [3] 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 Proc. 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of LIPIcs, pages 10:1–10:20, 2021.  doi:10.4230/LIPIcs.SoCG.2021.10.
  * [4] Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms.  Compacting squares: Input-sensitive in-place reconfiguration of sliding squares.  In Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), volume 227 of LIPIcs, pages 4:1–4:19, 2022.  doi:10.4230/LIPICS.SWAT.2022.4.
  * [5] Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O’Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer.  Efficient constant-velocity reconfiguration of crystalline robots.  Robotica, 29(1):59–71, 2011.  doi:10.1017/S026357471000072X.
  * [6] Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O’Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer.  Linear reconfiguration of cube-style modular robots.  Computational Geometry, 42(6):652 – 663, 2009.  doi:10.1016/j.comgeo.2008.11.003.
  * [7] Matthew Connor and Othon Michail.  Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes.  In Proc. 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022), volume 13707 of LNCS, pages 60–76. Springer, 2022.  doi:10.1007/978-3-031-22050-0\\_5.
  * [8] Adrian Dumitrescu and János Pach.  Pushing squares around.  Graphs and Combinatorics, 22:37–50, 2006.  doi:10.1007/s00373-005-0640-1.
  * [9] Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer.  Connected coordinated motion planning with bounded stretch.  In Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021), volume 212 of LIPIcs, pages 9:1–9:16, 2021.  doi:10.4230/LIPIcs.ISAAC.2021.9.
  * [10] Daniel Feshbach and Cynthia Sung.  Reconfiguring non-convex holes in pivoting modular cube robots.  IEEE Robotics and Automation Letters, 6(4):6701–6708, 2021.  doi:10.1109/LRA.2021.3095030.
  * [11] Robert Fitch, Zack Butler, and Daniela Rus.  Reconfiguration planning for heterogeneous self-reconfiguring robots.  In Proc. IEEE/RSJ International Conference on Intelligent Robots and System (IROS 2003), volume 3, pages 2460–2467, 2003.  doi:10.1109/IROS.2003.1249239.
  * [12] Ferran Hurtado, Enrique Molina, Suneeta Ramaswami, and Vera Sacristán.  Distributed reconfiguration of 2D lattice-based modular robotic systems.  Autonomous Robots, 38:383–413, 2015.  doi:10.1007/s10514-015-9421-8.
  * [13] Othon Michail, George Skretas, and Paul G. Spirakis.  On the transformation capability of feasible mechanisms for programmable matter.  In Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of LIPIcs, pages 136:1–136:15, 2017.  doi:10.4230/LIPICS.ICALP.2017.136.
  * [14] Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms.  Hiding sliding cubes: Why reconfiguring modular robots is not easy.  In Proc. 36th International Symposium on Computational Geometry, (SoCG 2020, Media Exposition), volume 164 of LIPIcs, pages 78:1–78:5, 2020\.  doi:10.4230/LIPICS.SOCG.2020.78.
  * [15] Joel Moreno and Vera Sacristán.  Reconfiguring sliding squares in-place by flooding.  In Proc. 36th European Workshop on Computational Geometry (EuroCG), pages 32:1–32:7, 2020.
  * [16] Irene Parada, Vera Sacristán, and Rodrigo I. Silveira.  A new meta-module design for efficient reconfiguration of modular robots.  Autonomous Robots, 45(4):457–472, 2021.  doi:10.1007/s10514-021-09977-6.
  * [17] Cynthia R. Sung, James M. Bern, John Romanishin, and Daniela Rus.  Reconfiguration planning for pivoting cube modular robots.  In Proc. IEEE International Conference on Robotics and Automation (ICRA 2015), pages 1933–1940, 2015.  doi:10.1109/ICRA.2015.7139451.