In micro- and nano-scale systems, particles can be moved by using an external force like gravity or a magnetic field. In the presence of adhesive particles that can attach to each other, the challenge is to decide whether a shape is constructible. Previous work provides a class of shapes for which constructibility can be decided efficiently, when particles move maximally into the same direction on actuation. In this paper, we consider a stronger model. On actuation, each particle moves one unit step into the given direction. We prove that deciding constructibility is NP-hard for three-dimensional shapes, and that a maximum constructible shape can be approximated. The same approximation algorithm applies for 2D. We further present linear-time algorithms to decide whether a tree-shape in 2D or 3D is constructible. If scaling is allowed, we show that the $c$-scaled copy of every non-degenerate polyomino is constructible, for every $c geq 2$.
Download