Size-dependent tile self-assembly: constant-height rectangles and stability

DOI10.1007/978-3-662-48971-0_26MaRDI QIDQ3459870zbMATH OpenOpenAlexFDO

Authors Sándor P. Fekete, Robert T. Schweller, Andrew Winslow

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.06898

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We introduce a new model of algorithmic tile self-assembly called size-dependent assembly. In previous models, supertiles are stable when the total strength of the bonds between any two halves exceeds some constant temperature. In this model, this constant temperature requirement is replaced by an nondecreasing temperature function $au:mathbbNightarrowmathbbN$ that depends on the size of the smaller of the two halves. This generalization allows supertiles to become unstable and break apart, and captures the increased forces that large structures may place on the bonds holding them together. We demonstrate the power of this model in two ways. First, we give fixed tile sets that assemble constant-height rectangles and squares of arbitrary input size given an appropriate temperature function. Second, we prove that deciding whether a supertile is stable is coNP-complete. Both results contrast with known results for fixed temperature.

Recommendations

• Program size and temperature in self-assembly
• Program size and temperature in self-assembly
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
• Complexities for generalized models of self-assembly

Cited in

(3)

• The complexity of multiple handed self-assembly
• ACTIVE TILE SELF-ASSEMBLY, PART 2: SELF-SIMILAR STRUCTURES AND STRUCTURAL RECURSION
• Geometric tiles and powers and limitations of geometric hindrance in self-assembly

This page was built for publication: Size-dependent tile self-assembly: constant-height rectangles and stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459870)