  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 $\Omega(N^{\frac{1}{3}})$; for
tree-shaped structures, we give an $O(N^{\frac{1}{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.
