Universal Coating by 3D Hybrid Programmable Matter
I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: Y. Emek (Ed.), Structural Information and Communication Complexity, Springer Nature Switzerland, Cham, 2024.
Download
No fulltext has been uploaded.
Book Chapter
| Published
| English
Author
Kostitsyna, Irina;
Liedtke, David JanLibreCat;
Scheideler, ChristianLibreCat
Book Editor
Emek, Yuval
Department
Abstract
Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid programmable matter. In this model, a single agent with strictly limited viewing range and the computational capability of a deterministic finite automaton can act on passive tiles by picking up a tile, moving, and placing it at some spot. The goal of the coating problem is to fill each node of some surface graph of size n with a tile. We first solve the problem on a restricted class of graphs with a single tile type, and then use constantly many tile types to encode this graph in certain surface graphs capturing the surface of 3D objects. Our algorithm requires O(n^2) steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions.
Keywords
Publishing Year
Book Title
Structural Information and Communication Complexity
ISBN
LibreCat-ID
Cite this
Kostitsyna I, Liedtke DJ, Scheideler C. Universal Coating by 3D Hybrid Programmable Matter. In: Emek Y, ed. Structural Information and Communication Complexity. Springer Nature Switzerland; 2024. doi:10.1007/978-3-031-60603-8_21
Kostitsyna, I., Liedtke, D. J., & Scheideler, C. (2024). Universal Coating by 3D Hybrid Programmable Matter. In Y. Emek (Ed.), Structural Information and Communication Complexity. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-60603-8_21
@inbook{Kostitsyna_Liedtke_Scheideler_2024, place={Cham}, title={Universal Coating by 3D Hybrid Programmable Matter}, DOI={10.1007/978-3-031-60603-8_21}, booktitle={Structural Information and Communication Complexity}, publisher={Springer Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}, editor={Emek, Yuval}, year={2024} }
Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Universal Coating by 3D Hybrid Programmable Matter.” In Structural Information and Communication Complexity, edited by Yuval Emek. Cham: Springer Nature Switzerland, 2024. https://doi.org/10.1007/978-3-031-60603-8_21.
I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Universal Coating by 3D Hybrid Programmable Matter,” in Structural Information and Communication Complexity, Y. Emek, Ed. Cham: Springer Nature Switzerland, 2024.
Kostitsyna, Irina, et al. “Universal Coating by 3D Hybrid Programmable Matter.” Structural Information and Communication Complexity, edited by Yuval Emek, Springer Nature Switzerland, 2024, doi:10.1007/978-3-031-60603-8_21.
Google Scholar
ISBN Search