Paper by Erik D. Demaine
- Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers, “Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor”, in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Dortmund, Germany, March 10–12, 2011, pages 201–212.
We consider a model of algorithmic self-assembly of geometric shapes out of
square Wang tiles studied in SODA 2010, in which there are two types of tiles
(e.g., constructed out of DNA and RNA material) and one operation that
destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all
RNA tiles). We show that a single use of this destruction operation enables
much more efficient construction of arbitrary shapes. In particular, an
arbitrary shape can be constructed using an asymptotically optimal number of
distinct tile types (related to the shape's Kolmogorov complexity), after
scaling the shape by only a logarithmic factor. By contrast, without the
destruction operation, the best such result has a scale factor at least linear
in the size of the shape and is connected only by a spanning tree of the
scaled tiles. We also characterize a large collection of shapes that can be
constructed efficiently without any scaling.
- The full paper is available as arXiv.org:1004.4383 of the Computing Research Repository (CoRR).
- Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.
- The paper is available in PDF (671k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2021 by