2018/05/16 by Joshua J. Daymude, Daymude, Joshua J., Robert Gmyr +9
Computer Science · Engineering · Physics and Astronomy · #Distributed #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #Micro and Nano Robotics #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.06149
openalex publication_date 2018/05/16 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/14
We envision programmable matter as a system of nano-scale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. We use the geometric amoebot model as our computational framework, which assumes particles move on the triangular lattice. Motivated by the problem of shape sealing whose goal is to seal an object using as little resources as possible, we investigate how a particle system can self-organize to form an object's convex hull. We give a fully distributed, local algorithm for convex hull formation and prove that it runs in O(B + Hlog H) asynchronous rounds, where B is the length of the object's boundary and H is the length of the object's convex hull. Our algorithm can be extended to also form the object's ortho-convex hull, which requires the same number of particles but additionally minimizes the enclosed space within the same asymptotic runtime.