License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.11
URN: urn:nbn:de:0030-drops-82214
URL: https://drops.dagstuhl.de/opus/volltexte/2017/8221/
Go to the corresponding LIPIcs Volume Portal


Becker, Aaron T. ; Fekete, Sándor P. ; Keldenich, Phillip ; Krupke, Dominik ; Rieck, Christian ; Scheffer, Christian ; Schmidt, Arne

Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces

pdf-format:
LIPIcs-ISAAC-2017-11.pdf (3 MB)


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 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.

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 Micro-Factories that Build Objects with Uniform External Forces}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8221},
  URN =		{urn:nbn:de:0030-drops-82214},
  doi =		{10.4230/LIPIcs.ISAAC.2017.11},
  annote =	{Keywords: Programmable matter, micro-factories, tile assembly, tilt, approximation, hardness}
}

Keywords: Programmable matter, micro-factories, tile assembly, tilt, approximation, hardness
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI