{"id":1034,"date":"2024-04-01T12:02:49","date_gmt":"2024-04-01T19:02:49","guid":{"rendered":"https:\/\/labs.engineering.asu.edu\/sops\/?page_id=1034"},"modified":"2024-04-01T12:02:49","modified_gmt":"2024-04-01T19:02:49","slug":"convex-hull","status":"publish","type":"page","link":"https:\/\/labs.engineering.asu.edu\/sops\/convex-hull\/","title":{"rendered":"Convex Hull Formation for Programmable Matter"},"content":{"rendered":"\n
<\/div>\n\n\n\n
\n
\n

Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Sheideler, and Andr\u00e9a W. Richa.
[arXiv<\/a>] [Online<\/a>] \u2014 Conference paper at the\u00a021st International Conference on Distributed Computing and Networking (ICDCN \u201920)<\/em>, pp. 2:1-2:10, 2020.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Overview<\/h2>\n\n\n\n

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\u2019s convex hull<\/strong>. We prove that this algorithm is correct and terminates within O(B<\/em>)<\/strong> asynchronous rounds, where B<\/strong><\/em> <\/em>is the length of the object\u2019s boundary. We also show that this algorithm can be extended to form an object\u2019s (weak) O-hull<\/strong>, which uses the same number of particles but \u201cshrink-wraps\u201d the object to enclose the minimum possible area.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\"\"<\/figure>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Our algorithms are the first to compute convex hulls with distributed entities that have\u00a0strictly local sensing<\/em>,\u00a0constant-size memory<\/em>, and\u00a0no shared sense of orientation or coordinates<\/em>. Ours is also the first distributed approach to computing\u00a0restricted-orientation convex hulls<\/strong>. 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\u00a0distributed binary counters<\/strong>\u00a0that efficiently support\u00a0increments<\/em>,\u00a0decrements<\/em>, and\u00a0zero-tests<\/em>\u00a0\u2014 even as the particles move.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\"\"<\/figure>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

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\u2019s 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.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\"\"<\/figure>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

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\u2019s been learned.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Resources<\/h2>\n\n\n\n