  The concept of programmable matter envisions a very large number of tiny and
simple robot particles forming a smart material. Even though the particles are
restricted to local communication, local movement, and simple computation,
their actions can nevertheless result in the global change of the material's
physical properties and geometry.
  A fundamental algorithmic task for programmable matter is to achieve global
shape reconfiguration by specifying local behavior of the particles. In this
paper we describe a new approach for shape reconfiguration in the amoebot
model. The amoebot model is a distributed model which significantly restricts
memory, computing, and communication capacity of the individual particles. Thus
the challenge lies in coordinating the actions of particles to produce the
desired behavior of the global system.
  Our reconfiguration algorithm is the first algorithm that does not use a
canonical intermediate configuration when transforming between arbitrary
shapes. We introduce new geometric primitives for amoebots and show how to
reconfigure particle systems, using these primitives, in a linear number of
activation rounds in the worst case. In practice, our method exploits the
geometry of the symmetric difference between input and output shape: it
minimizes unnecessary disassembly and reassembly of the particle system when
the symmetric difference between the initial and the target shapes is small.
Furthermore, our reconfiguration algorithm moves the particles over as many
parallel shortest paths as the problem instance allows.
