Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures

• DOI: 10.48550/arxiv.2401.17734
• Publication Date: 2024-01-31
• Authors: Kristian Hinnenthal; David Liedtke; Christian Scheideler
• Keywords: FOS: Computer and information sciences; Emerging Technologies (cs.ET); 3D Model; Finite Automaton; Computer Science - Data Structures and Algorithms; Programmable Matter; Computer Science - Emerging Technologies; Shape Formation; Data Structures and Algorithms (cs.DS); ddc:004; F.2.2; 004

This paper considers the shape formation problem within 3D hybrid model, where a single agent with strictly limited viewing range and computational capacity of deterministic finite automaton manipulates passive tiles through pick-up, movement, placement actions. The goal is to reconfigure set into specific termed an icicle. icicle, identified as dense, hole-free structure, strategically chosen function intermediate for more intricate tasks. It designed easy exploration by state agent, enabling identification that can be lifted without breaking connectivity. Compared line shape, icicle presents distinct advantages, including reduced diameter presence multiple removable tiles. We propose algorithm transforms arbitrary initially connected tile structure in $\mathcal{O}(n^3)$ steps, matching runtime from prior work. Our theoretical contribution accompanied extensive experimental analysis, indicating our decreases structures on average.