Infinite Object Coating in the Amoebot Model

AbstractThe term programmable matter refers to matter which has the ability to change its physical properties (shape,density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input orautonomous sensing. This has many applications like smart materials, autonomous monitoring and repair, andminimal invasive surgery. While programmable matter might have been considered pure science fiction more thantwo decades ago, in recent years a large amount of research has been conducted in this field. Often programmablematter is envisioned as a very large number of small locally interacting computational particles. We propose theAmoebot model, a new model which builds upon this vision of programmable matter. Inspired by the behaviorof amoeba, the Amoebot model offers a versatile framework to model self-organizing particles and facilitatesrigorous algorithmic research in the area of programmable matter. We present an algorithm for the problem of arXiv:1411.2356v1 [cs.ET] 10 Nov 2014 coating an infinite object under this model, and prove the correctness of the algorithm and that it is work-optimal.