Convex Hull Formation for Programmable Matter

Abstract

We envision programmable matter as a system of computationally limited devices (called particles) that are able to self-organize in order to achieve a desired collective goal without the need for central control or external intervention. In this paper, we present an algorithm for the convex hull problem, which, given a particle system $P$ that is connected to a static object $O$, reconfigures $P$ such that it forms the convex hull of $O$. Our preliminary analysis indicates that the algorithm runs in $\mathcal{O}(n+m)$ asynchronous rounds in the worst case, where $n = |P|$ and $m$ is the area occupied by $O$. This would be worst-case optimal when $n = O(m)$, since any algorithm solving the problem needs $\Omega(m)$ rounds in the worst case to move the first particle from the inner face of the convex hull to the outer face. Our algorithm relies only on local information (e.g., particles do not have unique identifiers, do not know n, and share no common global orientation or coordinate system), and requires only a constant amount of memory per particle.