2026-07-23T04:13:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8221 2024-03-06T10:41:46Z ddc:004 open_access

Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces Becker, Aaron T. Fekete, Sándor P. Keldenich, Phillip Krupke, Dominik Rieck, Christian Scheffer, Christian Schmidt, Arne Programmable matter micro-factories tile assembly tilt approximation hardness 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 N^(1/3); for tree-shaped 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron T. Becker and Sándor P. Fekete and Phillip Keldenich and Dominik Krupke and Christian Rieck and Christian Scheffer and Arne Schmidt 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.11 urn:nbn:de:0030-drops-82214 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.11 eng https://creativecommons.org/licenses/by/3.0/legalcode