Convex Hull Formation for Programmable Matter


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.

July 28, 2017 1:40 PM
George Washington University
Washington D.C., USA
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.