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

K. Hinnenthal, D. Liedtke, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024, p. 15:1–15:20.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
Hinnenthal, Kristian; Liedtke, David; Scheideler, Christian
Editor
Casteigts, Arnaud; Kuhn, Fabian
Abstract
This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pick-up, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an icicle. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in đť’Ş(nÂł) steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average.
Publishing Year
Proceedings Title
3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
forms.conference.field.series_title_volume.label
Leibniz International Proceedings in Informatics (LIPIcs)
Volume
292
Page
15:1–15:20
ISSN
LibreCat-ID

Cite this

Hinnenthal K, Liedtke D, Scheideler C. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In: Casteigts A, Kuhn F, eds. 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Vol 292. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2024:15:1–15:20. doi:10.4230/LIPIcs.SAND.2024.15
Hinnenthal, K., Liedtke, D., & Scheideler, C. (2024). Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In A. Casteigts & F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (Vol. 292, p. 15:1–15:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2024.15
@inproceedings{Hinnenthal_Liedtke_Scheideler_2024, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures}, volume={292}, DOI={10.4230/LIPIcs.SAND.2024.15}, booktitle={3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Hinnenthal, Kristian and Liedtke, David and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={15:1–15:20}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
Hinnenthal, Kristian, David Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), edited by Arnaud Casteigts and Fabian Kuhn, 292:15:1–15:20. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SAND.2024.15.
K. Hinnenthal, D. Liedtke, and C. Scheideler, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures,” in 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), 2024, vol. 292, p. 15:1–15:20, doi: 10.4230/LIPIcs.SAND.2024.15.
Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 15:1–15:20, doi:10.4230/LIPIcs.SAND.2024.15.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search