Tilt Assembly: Algorithms for Micro-Factories That Build Objects
with Uniform External Forces
Aaron T. Becker∗1 , Sándor P. Fekete2 , Phillip Keldenich2 , Dominik Krupke2 , Christian
Rieck2 , Christian Scheffer2 , and Arne Schmidt2

arXiv:1709.06299v1 [] 19 Sep 2017

1

Department of Electrical and Computer Engineering, University of Houston, USA.
atbecker@uh.edu
2
Department of Computer Science, TU Braunschweig, Germany. {s.fekete, p.keldenich,
d.krupke, c.rieck, c.scheffer, arne.schmidt}@tu-bs.de

Abstract
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three
dimensions from tiny particles, which has been proposed in the context of programmable matter and
self-assembly for building high-yield micro-factories. The underlying model has particles moving under
the influence of uniform external forces until they hit an obstacle; particles can bond when being forced
together with another appropriate particle.
Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise
to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes P
in 2D consisting of N unit-squares (“tiles”), we prove that TAP can be decided in O(N log N ) time. For
the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible
size), we show polyAPX-hardness: unless P=NP, MaxTAP cannot be approximated within a factor of
1
1
Ω(N 3 ); for tree-shaped structures, we give an O(N 2 )-approximation algorithm. For the efficiency of the
assembly process itself, we show that any constructible shape allows pipelined assembly, which produces
copies of P in O(1) amortized time, i.e., N copies of P in O(N ) time steps. These considerations can
be extended to three-dimensional objects: For the class of polycubes P we prove that it is NP-hard to
decide whether it is possible to construct a path between two points of P ; it is also NP-hard to decide
constructibility of a polycube P . Moreover, it is expAPX-hard to maximize a path from a given start
point.

1

Introduction

In recent years, progress on flexible construction at micro- and nano-scale has given rise to a large set of
challenges that deal with algorithmic aspects of programmable matter. Examples of cutting-edge application
areas with a strong algorithmic flavor include self-assembling systems, in which chemical and biological substances such as DNA are designed to form predetermined shapes or carry out massively parallel computations;
and swarm robotics, in which complex tasks are achieved through the local interactions of robots with highly
limited individual capabilities, including micro- and nano-robots.
Moving individual particles to their appropriate attachment locations when assembling a shape is difficult
because the small size of the particles limits the amount of onboard energy and computation. One successful
approach to dealing with this challenge is to use molecular diffusion in combination with cleverly designed sets
of possible connections: in DNA tile self-assembly, the particles are equipped with sophisticated bonds that
∗ Work

from this author was partially supported by National Science Foundation IIS-1553063 and IIS-1619278

1

ensure that only a predesigned shape is produced when mixing together a set of tiles, see [18]. The resulting
study of algorithmic tile self-assembly has given rise to an extremely powerful framework and produced a
wide range of impressive results. However, the required properties of the building material (which must be
specifically designed and finely tuned for each particular shape) in combination with the construction process
(which is left to chemical reactions, so it cannot be controlled or stopped until it has run its course) make
DNA self-assembly unsuitable for some applications.
An alternative method for controlling the eventual position of particles is to apply a uniform external
force, causing all particles to move in a given direction until they hit an obstacle or another blocked particle.
As two of us (Becker and Fekete, [1]) have shown in the past, combining this approach with custom-made
obstacles (instead of custom-made particles) allows complex rearrangements of particles, even in grid-like
environments with axis-parallel motion. The appeal of this approach is that it shifts the design complexity
from the building material (the tiles) to the machinery (the environment). As recent practical work by
Manzoor et al. [15] shows, it is possible to apply this to simple “sticky” particles that can be forced to bond,
see Fig. 1: the overall assembly is achieved by adding particles one at a time, attaching them to the existing
sub-assembly.

n
w

e
s

Figure 1: A practical demonstration of Tilt Assembly based on alginate (i.e., a gel made by combining a
powder derived from seaweed with water) particles [15]. (a) Alginate particles in initial positions. (b) After
control moves of he, s, w, n, e, si (for east, south, west, north), the alginate microrobots move to the shown
positions. (c) After hw, ni inputs, the system produces the first multi-microrobot polyomino. (d) The next
three microrobot polyominoes are produced after applying multiple he, s, w, ni cycles. (e) After the alginate
microrobots have moved through the microfluidic factory layout, the final 4-particle polyomino is generated.
Moreover, pipelining this process may result in efficient rates of production, see Fig. 2 [15].
One critical issue of this approach is the requirement of getting particles to their destination without
being blocked by or bonding to other particles. As Fig. 3 shows, this is not always possible, so there are some
shapes that cannot be constructed by Tilt Assembly.
This gives rise to a variety of algorithmic questions: (1) Can we decide efficiently whether a given
polyomino can be constructed by Tilt Assembly? (2) Can the resulting process be pipelined to yield low

2

n
w

e
s

Figure 2: (Top left) Initial setup of a seven-tile polyomino assembly; the composed shape is shown enlarged
on the lower left. The bipartite decomposition into blue and red particles is shown for greater clarity, but can
also be used for better control of bonds. The sequence of control moves is he, s, w, ni, i.e., a clockwise order.
(Bottom left) The situation after 18 control moves. (Right) The situation after 7 full cycles, i.e., after 28
control moves; shown are three parallel “factories”.

Figure 3: A polyomino (black) that cannot be constructed by Tilt Assembly: the last tile cannot be attached,
as it gets blocked by previously attached tiles.
amortized building time? (3) Can we compute a maximum-size subpolyomino that can be constructed? (4)
What can be said about three-dimensional versions of the problem?

1.1

Our Contribution

We present the results shown in Table 1.
Dimension

Decision

Maximization

2D (simple)

O(N log N ) (Sec. 3)

polyAPX -hard

Approximation
Constructible Path
√
Ω(N 1/3 ), O( N ) (Sec. 4) O(N log N )(Sec. 4)

polyAPX -hard

Ω(N 1/3 ),

3D (general) NP-hard

(Sec. 5)

-

(Sec. 4)

NP-hard

(Sec. 5)

Table 1: Results for Tilt Assembly Problem (TAP) and its maximization variant (MaxTAP)

1.2

Related Work

Assembling polyominoes with tiles has been considered intensively in the context of tile self-assembly. In
1998, Erik Winfree [18] introduced the abstract tile self-assembly model (aTAM), in which tiles have glue
types on each of the four sides and two tiles can stick together if their glue type matches and the bonding
strength is sufficient. Starting with a seed tile, tiles will continue to attach to the existing partial assembly
3

until they form a desired polyomino; the process stops when no further attachments are possible. Apart
from the aTAM, there are various other models like the two-handed tile self-assembly model (2HAM) [8] and
the hierarchical tile self-assembly model [9], in which we have no single seed but pairs of subassemblies that
can attach to each other. Furthermore, the staged self-assembly model [10, 11] allows greater efficiency by
assembling polyominoes in multiple bins which are gradually combined with the content of other bins.
All this differs from the model in Tilt Assembly, in which each tile has the same glue type on all four
sides, and tiles are added to the assembly one at a time by attaching them from the outside along a straight
line. This approach of externally movable tiles has actually been considered in practice at the microscale
level using biological cells and an MRI, see [12], [13], [4]. Becker et al. [5] consider this for the assembly of
a magnetic Gauß gun, which can be used for applying strong local forces by very weak triggers, allowing
applications such as micro-surgery.
Using an external force for moving the robots becomes inevitable at some scale because the energy capacity
decreases faster than the energy demand. A consequence is that all non-fixed robots/particles perform the
same movement, so all particles move in the same direction of the external force until they hit an obstacle or
another particle. These obstacles allow shaping the particle swarm. Designing appropriate sets of obstacles
and moves gives rise to a range of algorithmic problems. Deciding whether a given initial configuration of
particles in a given environment can be transformed into a desired target configuration is NP-hard [1], even in
a grid-like setting, whereas finding an optimal control sequence is shown to be PSPACE-complete by Becker
et al. [2]. However, if it is allowed to design the obstacles in the first place, the problems become much more
tractable [1]. Moreover, even complex computations become possible: If we allow additional particles of
double size (i.e., two adjacent fields), full computational complexity is achieved, see Shad et al. [16]. Further
related work includes gathering a particle swarm at a single position [14] and using swarms of very simple
robots (such as Kilobots) for moving objects [6]. For the case in which human controllers have to move
objects by such a swarm, Becker et al. [3] study different control options. The results are used by Shahrokhi
and Becker [17] to investigate an automatic controller.
Most recent and most closely related to our paper is the work by Manzoor et al. [15], who use global
control to assembly polyominoes in a pipelined fashion: after constructing the first polyomino, each cycle
of a small control sequence produces another polyomino. However, the algorithmic part is purely heuristic;
providing a thorough understanding of algorithms and complexity is the content of our paper.

2

Preliminaries

Polyomino: For a set P ⊂ Z2 of N grid points in the plane, the graph GP is the induced grid graph,
in which two vertices p1 , p2 ∈ P are connected if they are at unit distance. Any set P with connected grid graph GP gives rise to a polyomino by replacing each point p ∈ P by a unit square
centered at p, which is called a tile; for simplicity, we also use P to denote the polyomino when the
context is clear, and refer to GP as the dual graph of the polyomino; P is tree-shaped, if GP is a
tree. A polyomino is called hole-free or simple if and only if the grid graph induced by Z2 \P is connected.
Blocking sets: For each point p ∈ Z2 we define blocking sets Np , Sp ⊆ P as the set of all points q ∈ P that
are above or below p and |px − qx | ≤ 1. Analogously, we define the blocking sets Ep , Wp ⊆ P as the set
of all points q ∈ P that are to the right or to the left of p and |py − qy | ≤ 1.
Construction step: A construction step is defined by a direction (north, east, south, west, abbreviated
by n, e, s, w) from which a tile is added and a latitude/longitude l describing a column or row. The
tile arrives from (l, ∞) for north, (∞, l) for east, (l, −∞) for south, and (−∞, l) for west into the
corresponding direction until it reaches the first grid position that is adjacent to one occupied by an
existing tile. If there is no such tile, the polyomino does not change. We note that a position p can be
added to a polyomino P if and only if there is a point q ∈ P with ||p − q||1 = 1 and one of the four
4

t

(a) Removing t destroys decomposability. The
polyomino can be decomposed by starting with
the three tiles above t.

(b) Removing the red convex tile leaves the polyomino non-decomposable; it can be decomposed
by starting from the bottom or the sides.

Figure 4: Two polyominoes and their convex tiles (white). (a) Removing non-convex tiles may destroy
decomposability. (b) In case of non-simple polygons we may not be able to remove convex tiles.
blocking sets, Np , Ep , Sp or Wp , is empty. Otherwise, if none of these sets are empty, this position is
blocked.
Constructibility: Beginning with a seed tile at some position p, a polyomino P is constructible if and only
if there is a sequence σ = ((d1 , l1 ), (d2 , l2 ), . . . , (dN −1 , lN −1 )), such that the resulting polyomino P 0 ,
induced by successively adding tiles with σ, is equal to P . We allow the constructed polyomino P 0 to
be a translated copy of P . Reversing σ yields a decomposition sequence, i.e., a sequence of tiles getting
removed from P .

3

Constructibility of Simple Polyominoes

In this section we focus on hole-free (i.e., simple) polyominoes. We show that the problem of deciding whether
a given polyomino can be constructed can be solved in polynomial time. This decision problem can be defined
as follows.
Definition 1 (Tilt Assembly Problem). Given a polyomino P , the Tilt Assembly Problem ( TAP)
asks for a sequence of tiles constructing P , if P is constructible.

3.1

A Key Lemma

A simple observation is that construction and (restricted) decomposition are the same problem. This allows
us to give a more intuitive argument, as it is easier to argue that we do not lose connectivity when removing
tiles than it is to prove that we do not block future tiles.
Theorem 2. A polyomino P can be constructed if and only if it can be decomposed using a sequence of tile
removal steps that preserve connectivity. A construction sequence is a reversed decomposition sequence.
Proof. To prove this theorem, it suffices to consider a single step. Let P be a polyomino and t be a tile that
is removed from P into some direction l, leaving a polyomino P 0 . Conversely, adding t to P 0 from direction l
yields P , as there cannot be any tile that blocks t from reaching the correct position, or we would not be able
to remove t from P in direction l.
For hole-free polyominoes we can efficiently find a construction/decomposition sequence if one exists. The
key insight is that one can greedily remove convex tiles. A tile t is said to be convex if and only if there is a
2 × 2 square solely containing t; see Fig. 4. If a convex tile is not a cut tile, i.e., it is a tile whose removal
does not disconnect the polyomino, its removal does not interfere with the decomposability of the remaining
polyomino.
This conclusion is based on the observation that a minimal cut (i.e., a minimal set of vertices whose
removal leaves a disconnected polyomino) of cardinality two in a hole-free polyomino always consists of two
(possibly diagonally) adjacent tiles. Furthermore, we can always find such a removable convex tile in any
decomposable hole-free polyomino. This allows us to devise a simple greedy algorithm.
5

We start by showing that if we find a non-blocked convex tile that is not a cut tile, we can simply remove it.
It is important to focus on convex tiles, as the removal of non-convex tiles can harm the decomposability: see
Fig. 4a for an illustration. In non-simple polyominoes, the removal of convex tiles can destroy decomposability,
as demonstrated in Fig. 4b.
Lemma 3. Consider a non-blocked non-cut convex tile t in a hole-free polyomino P . The polyomino P − t is
decomposable if and only if P is decomposable.
Proof. The first direction is trivial: if P − t is decomposable, P is decomposable as well, because we can
remove the non-blocked tile t first and afterwards use the existing decomposition sequence for P − t. The
other direction requires some case distinctions. Suppose for contradiction that P is decomposable but P − t
is not, i.e., t is important for the later decomposition.
Consider a valid decomposition sequence for P and the first tile t0 we cannot remove if we were to remove
t in the beginning. W.l.o.g., let t0 be the first tile in this sequence (removing all previous tiles obviously does
not destroy the decomposability). When we remove t first, we are missing a tile, hence t0 cannot be blocked
but has to be a cut tile in the remaining polyomino P − t. The presence of t preserves connectivity, i.e.,
{t, t0 } is a minimal cut on P . Because P has no holes, then t and t0 must be diagonal neighbors, sharing the
neighbors a and b. Furthermore, by definition neither of t and t0 is blocked in some direction. We make a
case distinction on the relation of these two directions.
The directions are orthogonal (Fig. 5a). Either a or b is a non-blocked convex tile, because t and t0
are both non-blocked; w.l.o.g., let this be a. It is easy to see that independent of removing t or t0 first,
after removing a we can also remove the other one.
The directions are parallel (Fig. 5b). This case is slightly more involved. By assumption, we have a
decomposition sequence beginning with t0 . We show that swapping t0 with our convex tile t in this
sequence preserves feasibility.
The original sequence has to remove either a or b before it removes t, as otherwise the connection
between the two is lost when t0 is removed first. After either a or b is removed, t becomes a leaf and
can no longer be important for connectivity. Thus, we only need to consider the sequence until either a
or b is removed. The main observation is that a and b block the same tiles as t or t0 , except for tile c as
in Fig. 5b. However, when c is removed, it has to be a leaf, because a is still not removed and in the
original decomposition sequence, t0 has already been removed. Therefore, a tile d =
6 t0 would have to be
removed before c. Hence, the decomposition sequence remains feasible, concluding the proof.
Next we show that such a convex tile always exists if the polyomino is decomposable.
Lemma 4. Let P be a decomposable polyomino. Then there exists a convex tile that is removable without
destroying connectivity.
Proof. We prove this by contradiction based on two possible cases.
Assume P to be a decomposable polyomino in which no convex tile is removable. Because P is decomposable, there exists some feasible decomposition sequence S. Let Pconvex denote the set of convex tiles of P and
let t ∈ Pconvex be the first removed convex tile in the decomposition sequence S. By assumption, t cannot be
removed yet, so it is either blocked or a cut tile.
t is blocked. Consider the direction in which we would remove t. If it does not cut the polyomino, the
last blocking tile has to be convex (and would have to be removed before t), see Fig. 6a. If it cuts
the polyomino, the component cut off also must have a convex tile and the full component has to be
removed before t, see Fig. 6b. This is again a contradiction to t being the first convex tile to be removed
in S.
t is a cut tile. P − t consists of exactly two connected polyominoes, P1 and P2 . It is easy to see that
P1 ∩ Pconvex 6= ∅ and P2 ∩ Pconvex 6= ∅, because every polyomino of size n ≥ 2 has at least two convex
tiles of which at most one becomes non-convex by adding t. (A polyomino of size 1 is trivial.) Before
being able to remove t, either P1 or P2 has to be completely removed, including their convex tiles. This
is a contradiction to t being the first convex tile in S to be removed.
6

c a0 t
dt b

at
t0 b
(a) If the unblocked directions of t and t0 are orthogonal, one of the two adjacent tiles (w.l.o.g. a) cannot
have any further neighbors. There can also be no
tiles in the upper left corner, because the polyomino
cannot cross the two free directions of t and t0 (red
marks).

(b) If the unblocked directions of t and t0 are parallel,
there is only the tile c for which something can change
if we remove t before t0 .

Figure 5: The red marks indicate that no tile is at this position; the dashed outline represents the rest of the
polyomino.

t0
B

A

t

t

(a) If the removal direction of t is not crossed, the last
blocking tile has to be convex (and has to be removed
before).

(b) If the removal direction of t crosses P , then P gets
split into components A and B. Component B has a
convex tile t0 that needs to be removed before t.

Figure 6: Polyominoes for which no convex tile should be removable, showing the contradiction to t being the
first blocked convex tile in P getting removed.

3.2

An Efficient Algorithm

An iterative combination of these two lemmas proves the correctness of greedily removing convex tiles. As we
show in the next theorem, using a search tree technique allows an efficient implementation of this greedy
algorithm.
Theorem 5. A hole-free polyomino can be checked for decomposability/constructibility in time O(N log N ).
Proof. Lemma 3 allows us to remove any convex tile, as long as it is not blocked and does not destroy
connectivity. Applying the same lemma on the remaining polyomino iteratively creates a feasible decomposition
sequence. Lemma 4 proves that this is always sufficient. If and only if we can at some point no longer find a
matching convex tile (to which we refer as candidates), the polyomino cannot be decomposable.
Let B be the time needed to check whether a tile t is blocked. A naı̈ve way of doing this is to try out
all tiles and check if t gets blocked, requiring time O(N ). With a preprocessing step, we can decrease B to
O(log N ) by using O(N ) binary search trees for searching for blocking tiles and utilizing that removing a tile
can change the state of at most O(1) tiles. For every vertical line x and horizontal line y going through P ,
we create a balanced search tree, i.e., for a total of O(N ) search trees. An x-search tree for a vertical line x
contains tiles lying on x, sorted by their y-coordinate. Analogously define a y-search tree for a horizontal line
y containing tiles lying on y sorted by their x-coordinate. We iterate over all tiles t = (x, y) and insert the
7

Figure 7: When removing the red tile, only the orange tiles can become unblocked or convex.
tile in the corresponding x- and y-search tree with a total complexity of O(N log N ). Note that the memory
complexity remains linear, because every tile is in exactly two search trees. To check if a tile at position
(x0 , y 0 ) is blocked from above, we can simply search in the (x0 − 1)-, x0 - and (x0 + 1)-search tree for a tile with
y > y 0 . We analogously perform search queries for the other three directions, and thus have 12 queries of
total cost O(log N ).
We now iterate on all tiles and add all convex tiles that are not blocked and are not a cut tile to the set
F (cost O(N log N )). Note that checking whether a tile is a cut tile can be done in constant time, because
it suffices to look into the local neighborhood. While F is not empty, we remove a tile from F , from the
polyomino, and from its two search trees in time O(log N ). Next, we check the up to 12 tiles that are blocked
first from the removed tile for all four orientations, see Fig. 7. Only these tiles can become unblocked or
a convex tile. Those that are convex tiles, not blocked and no cut tile are added to F . All tiles behind
those cannot become unblocked as the first tiles would still be blocking them. The cost for this is again in
O(log N ). This is continued until F is empty, which takes at most O(N ) loops each of cost O(log N ). If the
polyomino has been decomposed, the polyomino is decomposable/constructible by the corresponding tile
sequence. Otherwise, there cannot exist such a sequence. By prohibiting to remove a specific tile, one can
force a specific start tile.

3.3

Pipelined Assembly

Given that a construction is always possible based on adding convex corners to a partial construction, we
can argue that the idea of Manzoor et al. [15] for pipelined assembly can be realized for every constructible
polyomino: We can transform the construction sequence into a spiral-shaped maze environment, as illustrated
in Fig. 8. This allows it to produce D copies of P in N + D cycles, implying that we only need 2N cycles for
N copies. It suffices to use a clockwise order of four unit steps (west, north, east, south) in each cycle.
The main idea is to create a spiral in which the assemblies move from the inside to the outside. The first
tile is provided by an initial south movement. After each cycle, ending with a south movement, the next seed
tile of the next copy of P is added. For every direction corresponding to the direction of the next tile added
by the sequence, we place a tile depot on the outside of the spiral, with a straight-line path to the location of
the corresponding attachment.
Theorem 6. Given a construction sequence σ := ((d1 , l1 ), . . . , (dN −1 , lN −1 )) that constructs a polyomino P ,
we can construct a maze environment for pipelined tilt assembly, such that constructing D copies of P needs
O(N + D) unit steps. In particular, constructing one copy of P can be done in amortized time O(1).
Proof. Consider the construction sequence σ, the movement sequence ζ consisting of N repetitions of the
cycle (w, n, e, s), and an injective function m : σ → ζ, with m((w, ·)) = e, m((n, ·)) = s, m(e, ·)) = w and
m((s, ·)) = n. We also require that m((di , li )) = ζj if for all i0 < i there is a j 0 < j with m((di0 , li0 )) = ζj 0 and
j is smallest possible. This implies that in each cycle there is at least one tile in σ mapped to one direction
in this cycle.

8

3

4

2
0

5
7

1

6

Figure 8: (Left) A polyomino P . Shown is the assembly order and the direction of attachment to the seed
(tile 0). (Right) A maze environment for pipelined construction of the desired polyomino P . After the fourth
cycle, each further cycle produces a new copy of P .
Labyrinth construction: The main part of the labyrinth is a spiral as can be seen in Fig. 8. Consider a
spiral that is making |ζ| many turns, and the innermost point q of this spiral. From q upwards, we
make a lane through the spiral until we are outside the spiral. At this point we add a depot of tiles,
such that after each south movement a new tile comes out of the depot (this can easily be done with
bottleneck constructions as seen in Fig. 8 or in [15]). Then, we proceed for each turn in the spiral as
follows: For the j-th turn, if m−1 (ζj ) is empty we do nothing. Else if m−1 (ζj ) is not empty we want to
add the next tile. Let ti be this particular tile. Then, we construct a lane in direction −ζj , i.e., the
direction from where the tile will come from, until we are outside the spiral. By shifting this line in an
orthogonal direction we can enforce the tile to fly in at the correct position relating to li . There, we
add a depot with tiles, such that the first tile comes out after j − 1 steps and with each further cycle a
new tile comes out (this can be done by using loops in the depot, see Fig. 8 or [15]). Depots, which
lie on the same side of the spiral, can be shifted arbitrarily, so they do not collide. These depots can
be made arbitrarily big, and thus, we can make as many copies of P as we wish. Note that we can
make the paths in the spiral big enough, such that after every turn the bounding box of the current
polyomino fits through the spiral.
Correctness: We will now show that we will obtain copies of P . Consider any j-th turn in the spiral,
where the i-th tile ti is going to be added to the current polyomino. With the next step, ti and the
polyomino move in direction ζj . While the polyomino does not touch the next wall in the spiral,
the distance between ti and the polyomino will not decrease. However when the polyomino hits the
wall the polyomino stops moving and ti continues moving towards the polyomino. Wall-hitting is the
same situation as in our non-parallel model: To a fixed polyomino we can add tiles from n, e, s or
w. Therefore, the tile connects to the correct place. Since this is true for any tile and any copy, we
conclude that every polyomino we build is indeed a copy of P .
Time: Since the spiral has at most 4N unit steps (or N cycles), the first polyomino will be constructed
after 4N unit steps. By construction, we began the second copy one cycle after beginning the first
copy, the third copy one cycle after the second, and so on. This means, after each cycle, when the first

9

0

0

1

1

Figure 9: Two different sequences. The red tile represents the bounding box of the current polyomino. (Left)
A desired sequence. The latitude intersects the bounding box. (Right) A sequence where the latitude does
not intersect the bounding box.
polyomino is constructed, we obtain another copy of P . Therefore, for D copies we need N + D cycles
(or O(N + D) unit steps). For D ∈ Ω(N ) this results in an amortized constant time construction for P .
Note that this proof only considers construction sequences in the following form: If a tile ti increases the
side length of the bounding box of the current polyomino, then the tile is added from a direction with a
longitude/latitude, such that the longitude/latitude intersects the bounding box (see Fig. 9). In the case
there is a tile, such that the longitude/latitude does not intersect the bounding box, then we can rotate the
direction by π2 towards the polyomino and we will have a desired construction sequence.

4

Optimization Variants in 2D

For polyominoes that cannot be assembled, it is natural to look for a maximum-size subpolyomino that
is constructible. This optimization variant is polyAPX-hard, i.e., we cannot hope for an approximation
1
algorithm with an approximation factor within Ω(N 3 ), unless P = NP.
Definition 7 (Maximum Tilt Assembly Problem). Given a polyomino P , the Maximum Tilt Assembly
Problem ( MaxTAP) asks for a sequence of tiles building a cardinality-maximal connected subpolyomino
P0 ⊆ P.
Theorem 8. MaxTAP is polyAPX-hard, even for tree-shaped polyominoes.
Proof. We reduce Maximum Independent Set (MIS) to MaxTAP; see Fig. 10 for an illustration. Consider
an instance G = (V, E) of MIS, which we transform into a polyomino PG . We construct PG as follows. Firstly,
construct a horizontal line from which we go down to select which vertex in G will be chosen. The line must
have length 10n − 9, where n = |V |. Every 10th tile will represent a vertex, starting with the first tile on the
line. Let ti be such a tile representing vertex vi . For every vi we add a selector gadget below ti and for every
{vi , vj } ∈ δ(vi ) we add a reflected selector gadget below tj , as shown in Fig. 10, each consisting of 19 tiles.
Note that all gadgets for selecting vertex vi are above the gadgets of vj if i < j and that there are at most n2
such gadgets. After all gadgets have been constructed, we have already placed at most 19n2 + 10n − 9 ≤ 29n2
tiles. We continue with a vertical line with a length of 30n2 tiles.
Now let α∗ be an optimal solution to MIS. Then MaxTAP has a maximum polyomino of size at least
30n2 α∗ and at most 30n2 α∗ + 29n2 : We take the complete vertical part of ti for every vi in the optimal
solution of MIS. Choosing other lines block the assembly of further lines and thus, yields a smaller solution.
Now suppose we had an N 1−ε -approximation for MaxTAP. Then we would have a solution of at least
1
∗
∗
∗
2 ∗
N 1−ε T , where T is the optimal solution. We know that an optimal solution has T ≥ 30n α tiles and the
30n2 α∗
3
2
3
polyomino has at most N ≤ 30n + 29n ≤ 59n tiles. Therefore, we have at least 591−ε n3−3ε tiles and thus
at least 591−ε1n3−3ε α∗ strips, because each strips is 30n2 tiles long. Consider some ε ≥ 23 + η for any η > 0,
then the number of strips is 591/31n1−3η α∗ which results in an n1−δ -approximation for MIS, contradicting the
inapproximability of MIS (unless P=NP) shown by Berman and Schnitger [7].
As a consequence of the construction, we get Corollary 9.
10

v1

v2

v3

v4

v2

v4

v1

v3
Figure 10: Reduction from MIS to MaxTAP. (Left) A graph G with four vertices. (Right) A polyomino
constructed for the reduction with a feasible, maximum solution marked in grey.
1

Corollary 9. Unless P = N P , MaxTAP cannot be approximated within a factor of Ω(N 3 ).
√
On the positive side, we can give an O( N )-approximation algorithm.
√
Theorem 10. The longest constructible path in a tree-shaped polyomino P is a N -approximation for
MaxTAP, and we can find such a path in polynomial time.
Proof. Consider an optimal solution P ∗ and a smallest enclosing box B containing P ∗ . Then there must be
two opposite sides of B having at least one tile of P ∗ . Consider
the path S between both tiles. Because the
√
area AB of B is at least the number of tiles in P ∗ , |S| ≥ AB and a longest,
constructible path in P has
√
length at least |S|, we conclude that the longest constructible path is a N -approximation.
To find such a path, we can search for every path between two tiles, check whether we can build this path,
and take the longest, constructible path.
Checking constructibility for O(N 2 ) possible paths is rather expensive. However, we can efficiently approximate the longest constructible path in a tree-shaped polyomino with the help of sequentially constructible
paths, i.e., the initial tile is a leaf in the final path.
Theorem 11. We can find a constructible path in a tree-shaped polyomino in O(N 2 log N ) time that has a
length of at least half the length of the longest constructible path.
Proof. We only search for paths that can be built sequentially. Clearly, the longest such path is at least half
as long as the longest path that can have its initial tile anywhere. We use the same search tree technique as
before to look for blocking tiles. Select a tile of the polyomino as the initial tile. Do a depth-first search and
for every tile in this search, check if it can be added to the path. If it cannot be added, skip all deeper tiles,
as they also cannot be added. During every step in the depth-first search, we only need to change a single
tile in the search trees, doing O(1) updates with O(log N ) cost. As we only consider O(N ) vertices in the
depth-first search, this results in a cost of O(N log N ) for a fixed start tile. It is trivial to keep track of the
longest such constructible path. Repeating this for every tile results in a running time of O(N 2 log N ).
In tree-shaped polyominoes, finding a constructible path is easy. For simple polyominoes, additional
arguments and data structures lead to a similar result.
Theorem 12. In simple polyominoes, finding the longest of all shortest paths that are sequentially constructible
takes O(N 2 log N ) time.
11

Before we start with the proof of Theorem 12, we show in the next two lemmas that it is sufficient to
consider shortest paths only, and that we can restrict ourselves to one specific shortest path between two
tiles. Hence, we just need to test a maximum of O(n2 ) different paths.
Lemma 13. In a sequentially constructible path, if there is a direct straight connection for a subpath, the
subpath can be replaced by the straight connection.

B

AB

p0
W’

L

A

p1
BA

Figure 11: A subpath W 0 and its shortcut L in green. To block L, A and B must exist. But then, either p0
or p1 (red tiles) will also be blocked. Therefore, also W 0 cannot be built.
Proof. Consider a sequentially constructible path W and a subpath W 0 ⊂ W that has a straight line L
connecting the startpoint and the endpoint of W 0 . W.l.o.g., L is a vertical line and we build from bottom to
top. Assume that (W \W 0 ) ∪ L is not constructible. Then at least two structures (which can be single tiles)
A and B must exist, preventing us from building L. Furthermore, these structures have to be connected via
a path (AB or BA, see Fig. 11). We observe that none of these connections can exist or otherwise, we cannot
build W (if AB exist, we cannot build the last tile p0 of L; if BA exist, we cannot build the first tile p1 of
W 0 ). Therefore, we can replace W 0 with L.
By repeating the construction of Lemma 13 we get a shortest path from tile t1 to t2 in the following
form: Let P1 , . . . , Pk be reflex tiles on the path from t1 to t2 . Furthermore, for every 1 ≤ i ≤ k − 1, the path
from Pi to Pi+1 is monotone. This property holds for every shortest path, or else we can use shortcuts as in
Lemma 13.
Lemma 14. If a shortest path between two tiles is sequentially constructible, then every shortest path between
these two tiles is sequentially constructible.
Proof. Consider a constructible shortest path W , a maximal subpath W 0 that is x-y-monotone, and a
bounding box B around W 0 . Due to L1 -metric, any x-y-monotone path within B is as long as W 0 . Suppose
some path within B is not constructible. Then we can use the same blocking argument as in Lemma 13 to
prove that W 0 cannot be constructible as well, contradicting that W is constructible.
Using Lemma 13 and Lemma 14, we are ready to prove Theorem 12.
Proof of Theorem 12. Because it suffices to check one shortest path between two tiles, we can look at
the BFS tree from each tile and then proceed like we did in Theorem 11. Thus, for each tile we perform a
BFS in time O(N ) and a DFS with blocking look-ups in time O(N log N ), which results in a total time of
O(N 2 log N ).

12

5

Three-Dimensional Shapes

An interesting and natural generalization of TAP is to consider three-dimensional shapes, i.e., polycubes. The
local considerations for simply connected two-dimensional shapes are no longer sufficient. In the following
we show that deciding whether a polycube is constructible is NP-hard. Moreover, it is NP-hard to check
whether there is a constructible path from a start cube s to an end cube t in a partial shape.
As a stepping stone, we start with a restricted version of the three-dimensional problem.
Theorem 15. It is NP-hard to decide if a polycube can be built by inserting tiles only from above, north,
east, south, and west.

x1 _ x2 _ x 3

x2 _ x3 _ x4

x1 _ x3 _ x4
n
e

w
s

x1

x1

x2

x2

x3

x3

x4

x4

Figure 12: Top-view on the polycube. There is a vertical part going south for the true and false assignment
of each variable. We start building at the top layer (blue) and have to block either the true or the false part
of each variable from above. The blocked parts have to be built with only inserting from east, west, and
south. For each clause, the parts of the inverted literals are modified to allow at most two of them being
built in this way. All other parts can simply be inserted from above in the end.
Proof. We prove hardness by a reduction from 3SAT. A visualization for the formula (x1 ∨ x2 ∨ x3 ) ∧ (x2 ∨
x3 ∨ x4 ) ∧ (x1 ∨ x3 ∨ x4 ) can be seen in Fig. 12. It consists of two layers of interest (and some further auxiliary
ones for space and forcing the seed tile by using the one-way gadget shown in Fig. 14). In the beginning, one
has to build a part of the top layer (highlighted in blue in the example, details in Fig. 13 (Right)). Forcing a
specific start tile can be done by a simple construction. For each variable we have to choose to block the
left (for assigning true) or the right (for assigning false) part of the lower layer. In the end, the remaining
parts of the upper layer can trivially be filled from above. The blocked parts of the lower layer then have to
be built with only inserting tiles from east, south, or west. In the end, the non-blocked parts can be filled
in from above. For each clause we use a part (as shown in Fig. 13 (Left)) that allows only at most two of
its three subparts to be built from the limited insertion directions. We attach these subparts to the three
variable values not satisfying the clause, i.e., the negated literals. This forces us to leave at least one negated
13

true

false

true

x1

x2

false

Figure 13: Top-view on the polycube. (Left) In the beginning we have to block the access from the top for
either the true or false part of the variable. The variable is assigned the blocked value. (Right) Three gadgets
for a clause. Only two of them can be built if the tiles are only able to come from the east, south, and west.
literal of the clause unblocked, and thus at least one literal of the clause to be true. Overall, this allows us to
build the blocked parts of the lower layers only if the blocking of the upper level corresponds to a satisfying
assignment. If we can build the true and the false parts of a variable in the beginning, any truth assignment
for the variable is possible.

out

in
in

out

Figure 14: (Left) This polyomino can only be constructed by starting at “in” and ending at “out”. (Right)
By adding layers above (white) and below (black) this polyomino starting at the “out”-tile, we obtain a
polycube that is only constructible by starting at “in” (from the other direction we must build the black
and white layer first and must then build the grey layer with 2D directions). Triangles denote where we can
switch to another layer. With this gadget we can enforce a seed tile.
The construction can be extended to assemblies with arbitrary direction.
Theorem 16. It is NP-hard to decide if a polycube can be built by inserting tiles from any direction.

14

Proof. We add an additional layer below the construction in Theorem 15 that has to be built first and blocks
access from below. Forcing the bottom layer to be built first can again be done with the one-way gadget
shown in Fig. 14.
The difficulties of construction in 3D are highlighted by the fact that even identifying constructible
connections between specific positions is NP-hard.
Theorem 17. It is NP-hard to decide whether a path from one tile to another can be built in a general
polycube.

x4

x2

AND

t

x1
x1

x2

x3

x4

x3

s

Figure 15: (Left) Circuit representation for the SAT formula (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x4 ) ∧ (x2 ∨ x3 ∨ x4 ) ∧
(x1 ∨ x3 ∨ x4 ) ∧ (x1 ∨ x2 ∨ x4 ). (Right) Reduction from SAT formula. Boxes represent variable boxes.
Proof. We prove NP-hardness by a reduction from SAT. For each variable we have two vertical lines, one for
the true setting, one for the false setting. Each clause gets a horizontal line and is connected with a variable
if it appears as literal in the clause, see Fig 15 (Left). We transform this representation into a tour problem
where, starting at a point s, one first has to go through either the true or false line of each variable and
then through all clause lines, see Fig. 15 (Right). The clause part is only passable if the path in at least one
crossing part (squares) does not cross, forcing us to satisfy at least one literal of a clause. As one has to go
through all clauses, t is only reachable if the selected branches for the variables equal a satisfying variable
assignment for the formula.
We now consider how to implement this as a polycube. The only difficult part is to allow a constructible
clause path if there is a free crossing. In Fig. 16 (Left), we see a variable box that corresponds to the crossing
of the variable path at the squares in Fig. 15 (Right). It blocks the core from further insertions. The clause
path has to pass at least one of these variable boxes in order to reach the other side. See Fig. 15 (Right) for
an example. Note that the corresponding clause parts can be built by inserting only from above and below,
so there are no interferences.

6

Conclusion/Future Work

We have provided a number of algorithmic results for Tilt Assembly. Various unsolved challenges remain.
What is the complexity of deciding TAP for non-simple polyominoes? While Lemma 4 can be applied to all
polyominoes, we cannot simply remove any convex tile. Can
√ we find a constructible path in a polyomino from
a given start and endpoint? This would help in finding a N -approximation for non-simple polyominoes. How
can we optimize the total makespan for constructing a shape? And what options exist for non-constructible
shapes?

15

Figure 16: (Left) Empty variable box. (Right) A clause line (blue) dips into a variable box. If the variable
box is built, then we cannot build the dip of the clause line.
An interesting approach may be to consider staged assembly, as shown in Fig. 17, where a shape gets
constructed by putting together subpolyominoes, instead of adding one tile at a time. This is similar to
staged tile self-assembly [10, 11]. This may also provide a path to sublinear assembly
times, as a hierarchical
√
assembly allows massive parallelization. We conjecture that a makespan of O( N ) for a polyomino with N
tiles can be achieved.
All this is left to future work.

Figure 17: (Left) A polyomino that cannot be constructed in the basic TAP model. (Right) Construction in
a staged assembly model by putting together subpolyominoes.

References
[1] A. T. Becker, E. D. Demaine, S. P. Fekete, G. Habibi, and J. McLurkin. Reconfiguring massive particle
swarms with limited, global control. In Proceedings of the International Symposium on Algorithms and
Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pages
51–66, 2013.
[2] A. T. Becker, E. D. Demaine, S. P. Fekete, and J. McLurkin. Particle computation: Designing worlds
to control robot swarms with only global signals. In Proceedings IEEE International Conference on
Robotics and Automation (ICRA), pages 6751–6756, 2014.
[3] A. T. Becker, C. Ertel, and J. McLurkin. Crowdsourcing swarm manipulation experiments: A massive
online user study with large swarms of simple robots. In Proceedings IEEE International Conference on
Robotics and Automation (ICRA), pages 2825–2830, 2014.
[4] A. T. Becker, O. Felfoul, and P. E. Dupont. Simultaneously powering and controlling many actuators
with a clinical MRI scanner. In Proceedings of the IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS), pages 2017–2023, 2014.
[5] A. T. Becker, O. Felfoul, and P. E. Dupont. Toward tissue penetration by MRI-powered millirobots using
a self-assembled Gauss gun. In Proceedings IEEE International Conference on Robotics and Automation
(ICRA), pages 1184–1189, 2015.

16

[6] A. T. Becker, G. Habibi, J. Werfel, M. Rubenstein, and J. McLurkin. Massive uniform manipulation:
Controlling large populations of simple robots with a common input signal. In Proceedings of the
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 520–527, 2013.
[7] P. Berman and G. Schnitger. On the complexity of approximating the independent set problem.
Information and Computation, 96(1):77–94, 1992.
[8] S. Cannon, E. D. Demaine, M. L. Demaine, S. Eisenstat, M. J. Patitz, R. Schweller, S. M. Summers, and
A. Winslow. Two hands are better than one (up to constant factors). In Proc. Int. Symp. on Theoretical
Aspects of Computer Science(STACS), pages 172–184, 2013.
[9] H.-L. Chen and D. Doty. Parallelism and time in hierarchical self-assembly. SIAM Journal on Computing,
46(2):661–709, 2017.
[10] E. D. Demaine, M. L. Demaine, S. P. Fekete, M. Ishaque, E. Rafalin, R. T. Schweller, and D. L. Souvaine.
Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing,
7(3):347–370, 2008.
[11] E. D. Demaine, S. P. Fekete, C. Scheffer, and A. Schmidt. New geometric algorithms for fully connected
staged self-assembly. Theoretical Computer Science, 671:4–18, 2017.
[12] P. S. S. Kim, A. T. Becker, Y. Ou, A. A. Julius, and M. J. Kim. Imparting magnetic dipole heterogeneity
to internalized iron oxide nanoparticles for microorganism swarm control. Journal of Nanoparticle
Research, 17(3):1–15, 2015.
[13] P. S. S. Kim, A. T. Becker, Y. Ou, M. J. Kim, et al. Swarm control of cell-based microrobots using a
single global magnetic field. In Proceedings of the International Conference on Ubiquitous Robotics and
Ambient Intelligence (URAI), pages 21–26, 2013.
[14] A. V. Mahadev, D. Krupke, J.-M. Reinhardt, S. P. Fekete, and A. T. Becker. Collecting a swarm in a
grid environment using shared, global inputs. In Proc. IEEE Int. Conf. Autom. Sci. and Eng. (CASE),
pages 1231–1236, 2016.
[15] S. Manzoor, S. Sheckman, J. Lonsford, H. Kim, M. J. Kim, and A. T. Becker. Parallel self-assembly
of polyominoes under uniform control inputs. IEEE Robotics and Automation Letters, 2(4):2040–2047,
2017.
[16] H. M. Shad, R. Morris-Wright, E. D. Demaine, S. P. Fekete, and A. T. Becker. Particle computation:
Device fan-out and binary memory. In Proceedings IEEE International Conference on Robotics and
Automation (ICRA), pages 5384–5389, 2015.
[17] S. Shahrokhi and A. T. Becker. Stochastic swarm control with global inputs. In Proceedings of the
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 421–427, 2015.
[18] E. Winfree. Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology, 1998.

17

