19 citations · 46 across the 18 of their papers we have counts for
4 papers · 1 filter
One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece
Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete +4
In this paper we explore the power of tile self-assembly models that extend the well-studied abstract Tile Assembly Model (aTAM) by permitting tiles of shapes beyond unit squares.…
Inapproximability of the Smallest Superpolyomino Problem
Andrew Winslow
We consider the \emph{smallest superpolyomino problem}: given a set of colored polyominoes, find the smallest polyomino containing each input polyomino as a subshape. This problem…
Hidden Mobile Guards in Simple Polygons
Sarah Cannon, Diane L. Souvaine, Andrew Winslow
We consider guarding classes of simple polygons using mobile guards (polygon edges and diagonals) under the constraint that no two guards may see each other. In contrast to most ot…
Two Hands Are Better Than One (up to constant factors)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine +5
We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two…