Abstract
We present algorithmic results for the parallel assembly of many microscale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and selfassembly for building highyield microfactories. 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 simplyconnected polyominoes P in 2D consisting of N unitsquares ("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 polyAPXhardness: unless P=NP, MaxTAP cannot be approximated within a factor of N^(1/3); for treeshaped structures, we give an N^(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 threedimensional objects: For the class of polycubes P we prove that it is NPhard to decide whether it is possible to construct a path between two points of P; it is also NPhard to decide constructibility of a polycube P. Moreover, it is expAPXhard to maximize a path from a given start point.
BibTeX  Entry
@InProceedings{becker_et_al:LIPIcs:2017:8221,
author = {Aaron T. Becker and S{\'a}ndor P. Fekete and Phillip Keldenich and Dominik Krupke and Christian Rieck and Christian Scheffer and Arne Schmidt},
title = {{Tilt Assembly: Algorithms for MicroFactories that Build Objects with Uniform External Forces}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {11:111:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8221},
URN = {urn:nbn:de:0030drops82214},
doi = {10.4230/LIPIcs.ISAAC.2017.11},
annote = {Keywords: Programmable matter, microfactories, tile assembly, tilt, approximation, hardness}
}
Keywords: 

Programmable matter, microfactories, tile assembly, tilt, approximation, hardness 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017) 
Issue Date: 

2017 
Date of publication: 

04.12.2017 