Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
dc.contributor.author | Becker, Aaron T. | |
dc.contributor.author | Fekete, Sándor P. | |
dc.contributor.author | Keldenich, Phillip | |
dc.contributor.author | Krupke, Dominik | |
dc.contributor.author | Rieck, Christian | |
dc.contributor.author | Scheffer, Christian | |
dc.contributor.author | Schmidt, Arne | |
dc.date.accessioned | 2019-10-01T15:39:45Z | |
dc.date.available | 2019-10-01T15:39:45Z | |
dc.date.issued | 8/3/2018 | |
dc.description.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 $\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. | |
dc.identifier | 10.1007/s00453-018-0483-9 | |
dc.identifier.citation | Copyright 2018 Algorithmica. This is a post-print version of a published paper that is available at: https://link.springer.com/article/10.1007/s00453-018-0483-9 Recommended citation: Becker, Aaron T., Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt. "Tilt assembly: algorithms for micro-factories that build objects with uniform external forces." Algorithmica (2017): 1-23. DOI: 10.1007/s00453-018-0483-9 This item has been deposited in accordance with publisher copyright and licensing terms and with author's permission. | |
dc.identifier.uri | https://hdl.handle.net/10657/4907 | |
dc.language.iso | en_US | |
dc.publisher | Algorithmica | |
dc.subject | Programmable matter | |
dc.subject | Micro-factories | |
dc.subject | Tile assembly | |
dc.subject | Tilt | |
dc.subject | Approximation | |
dc.subject | Hardness | |
dc.title | Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces | |
dc.type | Article |