Convex Hull Formation for Programmable Matter
Convex Hull Formation for Programmable Matter
复制标题
可编程物质的凸包构造
DOI：
10.1145/3369740.3372916
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Richa, Andréa W.
中科院分区：
文献类型：
--
作者：
Daymude, Joshua J.;Gmyr, Robert;Hinnenthal, Kristian;Kostitsyna, Irina;Scheideler, Christian;Richa, Andréa W.
我们设想可编程物质是一个由纳米级的物质(称为粒子)组成的系统，具有非常有限的计算能力，它们共同移动和计算以实现预期的目标。受使用最少资源密封对象的问题的启发，我们展示了粒子系统如何自组织以形成对象的凸壳。给出了一种分布式局部凸壳生成算法，并证明了该算法运行在O(B)个异步轮次内，其中B是对象边界的长度。在相同的渐近运行时间内，该算法可以扩展为也形成对象的(弱)O-壳，它使用相同数量的粒子，但最小化被壳包围的面积。我们的算法是第一个使用分布式实体计算凸壳的算法，这些实体具有严格的局部感知、恒定大小的存储空间，并且没有共享的方向感或坐标。我们的方法也是第一个计算受限方向凸壳的分布式方法。这种方法涉及将粒子作为分布式内存进行协调；因此，作为一个支持但独立的结果，我们提出并分析了一种将具有恒定大小内存的粒子组织为分布式二进制计数器的算法，该算法有效地支持递增、递减和零测试-即使在粒子移动时也是如此。
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.
登录
查看更多内容
有限自动机机器人的形状识别
DOI：
10.4230/lipics.mfcs.2018.52
发表时间：
2018
期刊：
Proceedings.Seventh IEEE Symposium on Parallel and Distributed Processing
影响因子：
--
作者：
R. Gmyr;Kristian Hinnenthal;I. Kostitsyna;F. Kuhn;Dorian Rudolph;C. Scheideler
通讯作者：
C. Scheideler
影响因子：
2.1
作者：
Daymude, Joshua J.;Derakhshandeh, Zahra;Strothmann, Thim
通讯作者：
Strothmann, Thim
影响因子：
1.5
作者：
Per;J. Katajainen;C. Levcopoulos;O. Petersson
通讯作者：
O. Petersson
限制方向凸性
影响因子：
5.7
作者：
Eugene Fink;D. Wood
通讯作者：
D. Wood
趋光性超级粒子
影响因子：
0.9
作者：
Savoie, William;Cannon, Sarah;Daymude, Joshua J.;Warkentin, Ross;Li, Shengkai;Richa, Andréa W.;Randall, Dana;Goldman, Daniel I.
通讯作者：
Goldman, Daniel I.