---
_id: '54807'
abstract:
- lang: eng
  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 \U0001D4AA(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."
author:
- first_name: Kristian
  full_name: Hinnenthal, Kristian
  id: '32229'
  last_name: Hinnenthal
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  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>'
  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>'
  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)} }'
  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>.'
  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>.'
  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.'
date_created: 2024-06-18T07:45:34Z
date_updated: 2024-07-18T09:32:49Z
department:
- _id: '79'
doi: 10.4230/LIPIcs.SAND.2024.15
editor:
- first_name: Arnaud
  full_name: Casteigts, Arnaud
  last_name: Casteigts
- first_name: Fabian
  full_name: Kuhn, Fabian
  last_name: Kuhn
intvolume: '       292'
keyword:
- Programmable Matter
- Shape Formation
- 3D Model
- Finite Automaton
language:
- iso: eng
page: 15:1–15:20
place: Dagstuhl, Germany
publication: 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
publication_identifier:
  isbn:
  - 978-3-95977-315-7
  issn:
  - 1868-8969
publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: 'Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for
  Low Diameter Intermediate Structures'
type: conference
user_id: '55557'
volume: 292
year: '2024'
...
---
_id: '54802'
abstract:
- lang: eng
  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.
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
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
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>'
  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>
  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} }'
  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.'
  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>.
  short: 'I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: Y. Emek (Ed.), Structural
    Information and Communication Complexity, Springer Nature Switzerland, Cham, 2024.'
date_created: 2024-06-18T07:36:04Z
date_updated: 2024-07-18T09:32:58Z
department:
- _id: '79'
doi: 10.1007/978-3-031-60603-8_21
editor:
- first_name: Yuval
  full_name: Emek, Yuval
  last_name: Emek
keyword:
- Programmable Matter
- Coating
- Finite Automaton
- 3D
language:
- iso: eng
place: Cham
publication: Structural Information and Communication Complexity
publication_identifier:
  isbn:
  - '9783031606021'
  - '9783031606038'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
status: public
title: Universal Coating by 3D Hybrid Programmable Matter
type: book_chapter
user_id: '55557'
year: '2024'
...
---
_id: '1813'
author:
- first_name: Sandor
  full_name: P. Fekete, Sandor
  last_name: P. Fekete
- first_name: Andrea
  full_name: W. Richa, Andrea
  last_name: W. Richa
- first_name: Kay
  full_name: Römer, Kay
  last_name: Römer
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
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>
  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>
  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} }'
  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>.'
  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.
  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.
date_created: 2018-03-27T11:24:15Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '79'
doi: 10.1145/3106700.3106713
issue: '2'
page: 87--94
publication: SIGACT News
status: public
title: Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271
type: journal_article
user_id: '15504'
year: '2017'
...