Randomized self-assembly for approximate shapes

Ming-Yang Kao*, Robert Schweller

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

51 Scopus citations

Abstract

In this paper we design tile self-assembly systems which assemble arbitrarily close approximations to target squares with arbitrarily high probability. This is in contrast to previous work which has only considered deterministic assemblies of a single shape. Our technique takes advantage of the ability to assign tile concentrations to each tile type of a self-assembly system. Such an assignment yields a probability distribution over the set of possible assembled shapes. We show that by considering the assembly of close approximations to target shapes with high probability, as opposed to exact deterministic assembly, we are able to achieve significant reductions in tile complexity. In fact, we restrict ourselves to constant sized tile systems, encoding all information about the target shape into the tile concentration assignment. In practice, this offers a potentially useful tradeoff, as large libraries of particles may be infeasible or require substantial effort to create, while the replication of existing particles to adjust relative concentration may be much easier. To illustrate our technique we focus on the assembly of n×n squares, a special case class of shapes whose study has proven fruitful in the development of new self-assembly systems.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages370-384
Number of pages15
EditionPART 1
DOIs
StatePublished - 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/TerritoryIceland
CityReykjavik
Period7/7/087/11/08

Keywords

  • Approximation Algorithms
  • Randomized Algorithms
  • Self-Assembly

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Randomized self-assembly for approximate shapes'. Together they form a unique fingerprint.

Cite this