Convex Hull Formation for Programmable Matter
Overview
Motivated by the problem of sealing an object using minimal resources, this paper gives a distributed, local algorithm under the amoebot model for forming an object’s convex hull. We prove that this algorithm is correct and terminates within O(B) asynchronous rounds, where B is the length of the object’s boundary. We also show that this algorithm can be extended to form an object’s (weak) O-hull, which uses the same number of particles but “shrink-wraps” the object to enclose the minimum possible area.
Our algorithms are the first to compute convex hulls with distributed entities that have strictly local sensing, constant-size memory, and no shared sense of orientation or coordinates. Ours is also the first distributed approach to computing restricted-orientation convex hulls. This approach involves coordinating particles as distributed memory; thus, as a supporting but independent result, we present and analyze an algorithm for organizing particles with constant-size memory as distributed binary counters that efficiently support increments, decrements, and zero-tests — even as the particles move.
The core idea of our algorithm is the following: we treat the convex hull as an intersection of six half-planes, labelling the half-planes according to some internal compass. Then, a leader particle traverses the object’s boundary, keeping track of its distance to each of the six half-planes. Whenever its boundary traversal takes it past where it had estimated one or more half-planes to be, it updates its estimate. Thus, once it completes its traversal, it has an accurate estimate of the convex hull.
However, these distances can far exceed the memory capacity of a single particle. This is where the distributed binary counters come in: by using its follower particles as distributed memory, the leader can keep track of these large distances. The remainder of the algorithm involves carefully coordinating the particle system to fill the hull once it’s been learned.
Resources
- [GitHub] Coming soon!
- [Talk Slides] Coming soon!
Press
None.
BibTeX
@InProceedings{Daymude2020,
Title = {Convex Hull Formation for Programmable Matter},
Author = {Daymude, Joshua J. and Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Scheideler, Christian and Richa, Andr\'{e}a W.}, Booktitle = {Proceedings of the 21st International Conference on Distributed Computing and Networking},
Series = {ICDCN 2020},
Pages = {2:1–2:10},
Year = {2020} }
Related Publications
This paper is related in part to the Collaborative Computation paper (2018) which also studied binary counters under the amoebot model. However, as discussed in the Overview, this paper supplants those results by extending the counters to handle both increments and decrements by one as well as zero-testing.