[{"type":"conference","publication":"3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)","status":"public","editor":[{"last_name":"Casteigts","full_name":"Casteigts, Arnaud","first_name":"Arnaud"},{"first_name":"Fabian","last_name":"Kuhn","full_name":"Kuhn, Fabian"}],"abstract":[{"text":"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.","lang":"eng"}],"user_id":"55557","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","department":[{"_id":"79"}],"_id":"54807","language":[{"iso":"eng"}],"keyword":["Programmable Matter","Shape Formation","3D Model","Finite Automaton"],"publication_identifier":{"isbn":["978-3-95977-315-7"],"issn":["1868-8969"]},"citation":{"apa":"Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2024). Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In A. Casteigts &#38; F. Kuhn (Eds.), <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i> (Vol. 292, p. 15:1–15:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>","mla":"Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 15:1–15:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>.","short":"K. Hinnenthal, D.J. 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.","bibtex":"@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={<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>}, 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 Jan and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={15:1–15:20}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","ama":"Hinnenthal K, Liedtke DJ, Scheideler C. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In: Casteigts A, Kuhn F, eds. <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>. Vol 292. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2024:15:1–15:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>","ieee":"K. Hinnenthal, D. J. Liedtke, and C. Scheideler, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures,” in <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, 2024, vol. 292, p. 15:1–15:20, doi: <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>.","chicago":"Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” In <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, 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. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>."},"page":"15:1–15:20","intvolume":"       292","year":"2024","place":"Dagstuhl, Germany","date_created":"2024-06-18T07:45:34Z","author":[{"first_name":"Kristian","id":"32229","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal"},{"first_name":"David Jan","last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"volume":292,"date_updated":"2024-07-18T09:32:49Z","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.SAND.2024.15","title":"Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures"},{"date_updated":"2024-07-18T09:32:58Z","publisher":"Springer Nature Switzerland","author":[{"first_name":"Irina","full_name":"Kostitsyna, Irina","last_name":"Kostitsyna"},{"first_name":"David Jan","full_name":"Liedtke, David Jan","id":"55557","last_name":"Liedtke"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"date_created":"2024-06-18T07:36:04Z","title":"Universal Coating by 3D Hybrid Programmable Matter","doi":"10.1007/978-3-031-60603-8_21","publication_status":"published","publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783031606021","9783031606038"]},"place":"Cham","year":"2024","citation":{"ama":"Kostitsyna I, Liedtke DJ, Scheideler C. Universal Coating by 3D Hybrid Programmable Matter. In: Emek Y, ed. <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland; 2024. doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>","chicago":"Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Universal Coating by 3D Hybrid Programmable Matter.” In <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek. Cham: Springer Nature Switzerland, 2024. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>.","ieee":"I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Universal Coating by 3D Hybrid Programmable Matter,” in <i>Structural Information and Communication Complexity</i>, Y. Emek, Ed. Cham: Springer Nature Switzerland, 2024.","short":"I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: Y. Emek (Ed.), Structural Information and Communication Complexity, Springer Nature Switzerland, Cham, 2024.","bibtex":"@inbook{Kostitsyna_Liedtke_Scheideler_2024, place={Cham}, title={Universal Coating by 3D Hybrid Programmable Matter}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>}, 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} }","mla":"Kostitsyna, Irina, et al. “Universal Coating by 3D Hybrid Programmable Matter.” <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek, Springer Nature Switzerland, 2024, doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>.","apa":"Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2024). Universal Coating by 3D Hybrid Programmable Matter. In Y. Emek (Ed.), <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>"},"_id":"54802","user_id":"55557","department":[{"_id":"79"}],"keyword":["Programmable Matter","Coating","Finite Automaton","3D"],"language":[{"iso":"eng"}],"type":"book_chapter","publication":"Structural Information and Communication Complexity","abstract":[{"text":"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.","lang":"eng"}],"editor":[{"full_name":"Emek, Yuval","last_name":"Emek","first_name":"Yuval"}],"status":"public"},{"status":"public","type":"journal_article","publication":"SIGACT News","user_id":"15504","department":[{"_id":"79"}],"_id":"1813","citation":{"ama":"P. Fekete S, W. Richa A, Römer K, Scheideler C. Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271. <i>SIGACT News</i>. 2017;(2):87--94. doi:<a href=\"https://doi.org/10.1145/3106700.3106713\">10.1145/3106700.3106713</a>","ieee":"S. P. Fekete, A. W. Richa, K. Römer, and C. Scheideler, “Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271,” <i>SIGACT News</i>, no. 2, pp. 87--94, 2017.","chicago":"P. Fekete, Sandor, Andrea W. Richa, Kay Römer, and Christian Scheideler. “Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271.” <i>SIGACT News</i>, no. 2 (2017): 87--94. <a href=\"https://doi.org/10.1145/3106700.3106713\">https://doi.org/10.1145/3106700.3106713</a>.","bibtex":"@article{P. Fekete_W. Richa_Römer_Scheideler_2017, title={Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271}, DOI={<a href=\"https://doi.org/10.1145/3106700.3106713\">10.1145/3106700.3106713</a>}, number={2}, journal={SIGACT News}, author={P. Fekete, Sandor and W. Richa, Andrea and Römer, Kay and Scheideler, Christian}, year={2017}, pages={87--94} }","mla":"P. Fekete, Sandor, et al. “Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271.” <i>SIGACT News</i>, no. 2, 2017, pp. 87--94, doi:<a href=\"https://doi.org/10.1145/3106700.3106713\">10.1145/3106700.3106713</a>.","short":"S. P. Fekete, A. W. Richa, K. Römer, C. Scheideler, SIGACT News (2017) 87--94.","apa":"P. Fekete, S., W. Richa, A., Römer, K., &#38; Scheideler, C. (2017). Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271. <i>SIGACT News</i>, (2), 87--94. <a href=\"https://doi.org/10.1145/3106700.3106713\">https://doi.org/10.1145/3106700.3106713</a>"},"page":"87--94","year":"2017","issue":"2","doi":"10.1145/3106700.3106713","title":"Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271","date_created":"2018-03-27T11:24:15Z","author":[{"full_name":"P. Fekete, Sandor","last_name":"P. Fekete","first_name":"Sandor"},{"first_name":"Andrea","full_name":"W. Richa, Andrea","last_name":"W. Richa"},{"first_name":"Kay","full_name":"Römer, Kay","last_name":"Römer"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"date_updated":"2022-01-06T06:53:26Z"}]