TY - GEN
T1 - Convex Hull Formation for Programmable Matter
AU - Daymude, Joshua J.
AU - Gmyr, Robert
AU - Hinnenthal, Kristian
AU - Kostitsyna, Irina
AU - Scheideler, Christian
AU - Richa, Andréa W.
N1 - Funding Information:
Daymude and Richa are supported in part by the National Science Foundation under awards CCF-1422603, CCF-1637393, and CCF-1733680. Hinnenthal and Scheideler are supported by the German Research Foundation (DFG) under Project SCHE 1592/6-1.
Publisher Copyright:
© 2020 ACM.
PY - 2020
Y1 - 2020
N2 - We envision programmable matter as a system of nanoscale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. Motivated by the problem of sealing an object using minimal resources, we show how a particle system can self-organize to form an object's convex hull. We give a distributed, local algorithm for convex hull formation and prove that it runs in O(B) asynchronous rounds, where B is the length of the object's boundary. Within the same asymptotic runtime, this algorithm can be extended to also form the object's (weak) O-hull, which uses the same number of particles but minimizes the area enclosed by the hull. 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.
AB - We envision programmable matter as a system of nanoscale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. Motivated by the problem of sealing an object using minimal resources, we show how a particle system can self-organize to form an object's convex hull. We give a distributed, local algorithm for convex hull formation and prove that it runs in O(B) asynchronous rounds, where B is the length of the object's boundary. Within the same asymptotic runtime, this algorithm can be extended to also form the object's (weak) O-hull, which uses the same number of particles but minimizes the area enclosed by the hull. 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.
KW - computational geometry
KW - convex hull
KW - distributed algorithms
KW - programmable matter
KW - restricted-orientation geometry
KW - self-organization
UR - http://www.scopus.com/inward/record.url?scp=85098011751&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85098011751&partnerID=8YFLogxK
U2 - 10.1145/3369740.3372916
DO - 10.1145/3369740.3372916
M3 - Conference contribution
AN - SCOPUS:85098011751
SN - 9781450377515
T3 - ACM International Conference Proceeding Series
BT - ACM International Conference Proceeding Series
PB - Association for Computing Machinery
T2 - 21st International Conference on Distributed Computing and Networking, ICDCN 2020
Y2 - 4 January 2020 through 7 January 2020
ER -