---
_id: '64259'
abstract:
- lang: eng
  text: Shape formation is one of the most thoroughly studied problems in programmable
    matter and swarm robotics. However, in many models, the class of shapes that can
    be formed is highly restricted due to the particles’ limited memory. In the hybrid
    model, an active agent with the computational power of a deterministic finite
    automaton can form shapes by lifting and placing passive tiles on the triangular
    lattice. We study the shape reconfiguration problem where the agent additionally
    has the ability to distinguish so-called target nodes from non-target nodes and
    needs to form a target shape from the initial tile configuration. We present a
    worst-case optimal O(mn) algorithm for simply connected target shapes, where m
    is the initial number of unoccupied target nodes and n is the total number of
    tiles. Furthermore, we show how an agent can reconfigure a large class of target
    shapes with holes in O(n^4) steps.
author:
- first_name: Jonas
  full_name: Friemel, Jonas
  last_name: Friemel
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
- first_name: Christian
  full_name: Scheffer, Christian
  last_name: Scheffer
citation:
  ama: 'Friemel J, Liedtke DJ, Scheffer C. Tile Reconfiguration by a Finite Automaton.
    In: Di Giacomo E, Mondal D, eds. <i>WALCOM: Algorithms and Computation</i>. Springer
    Nature Singapore; 2026:512-526. doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>'
  apa: 'Friemel, J., Liedtke, D. J., &#38; Scheffer, C. (2026). Tile Reconfiguration
    by a Finite Automaton. In E. Di Giacomo &#38; D. Mondal (Eds.), <i>WALCOM: Algorithms
    and Computation</i> (pp. 512–526). Springer Nature Singapore. <a href="https://doi.org/10.1007/978-981-95-7127-7_34">https://doi.org/10.1007/978-981-95-7127-7_34</a>'
  bibtex: '@inproceedings{Friemel_Liedtke_Scheffer_2026, place={Singapore}, title={Tile
    Reconfiguration by a Finite Automaton}, DOI={<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>},
    booktitle={WALCOM: Algorithms and Computation}, publisher={Springer Nature Singapore},
    author={Friemel, Jonas and Liedtke, David Jan and Scheffer, Christian}, editor={Di
    Giacomo, Emilio and Mondal, Debajyoti}, year={2026}, pages={512–526} }'
  chicago: 'Friemel, Jonas, David Jan Liedtke, and Christian Scheffer. “Tile Reconfiguration
    by a Finite Automaton.” In <i>WALCOM: Algorithms and Computation</i>, edited by
    Emilio Di Giacomo and Debajyoti Mondal, 512–26. Singapore: Springer Nature Singapore,
    2026. <a href="https://doi.org/10.1007/978-981-95-7127-7_34">https://doi.org/10.1007/978-981-95-7127-7_34</a>.'
  ieee: 'J. Friemel, D. J. Liedtke, and C. Scheffer, “Tile Reconfiguration by a Finite
    Automaton,” in <i>WALCOM: Algorithms and Computation</i>, Perugia, Italy, 2026,
    pp. 512–526, doi: <a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>.'
  mla: 'Friemel, Jonas, et al. “Tile Reconfiguration by a Finite Automaton.” <i>WALCOM:
    Algorithms and Computation</i>, edited by Emilio Di Giacomo and Debajyoti Mondal,
    Springer Nature Singapore, 2026, pp. 512–26, doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>.'
  short: 'J. Friemel, D.J. Liedtke, C. Scheffer, in: E. Di Giacomo, D. Mondal (Eds.),
    WALCOM: Algorithms and Computation, Springer Nature Singapore, Singapore, 2026,
    pp. 512–526.'
conference:
  end_date: 2026-03-06
  location: Perugia, Italy
  name: 20th International Conference and Workshops on Algorithms and Computation
    (WALCOM)
  start_date: 2026-03-04
date_created: 2026-02-19T10:57:30Z
date_updated: 2026-02-19T11:03:38Z
doi: 10.1007/978-981-95-7127-7_34
editor:
- first_name: Emilio
  full_name: Di Giacomo, Emilio
  last_name: Di Giacomo
- first_name: Debajyoti
  full_name: Mondal, Debajyoti
  last_name: Mondal
language:
- iso: eng
page: 512-526
place: Singapore
publication: 'WALCOM: Algorithms and Computation'
publication_identifier:
  isbn:
  - 978-981-95-7127-7
publication_status: published
publisher: Springer Nature Singapore
status: public
title: Tile Reconfiguration by a Finite Automaton
type: conference
user_id: '55557'
year: '2026'
...
---
_id: '62285'
abstract:
- lang: eng
  text: 'The sliding square model is a widely used abstraction for studying self-reconfigurable
    robotic systems, where modules are square-shaped robots that move by sliding or
    rotating over one another. In this paper, we propose a novel distributed algorithm
    that enables a group of modules to reconfigure into a rhombus shape, starting
    from an arbitrary side-connected configuration. It is connectivity-preserving
    and operates under minimal assumptions: one leader module, common chirality, constant
    memory per module, and visibility and communication restricted to immediate neighbors.
    Unlike prior work, which relaxes the original sliding square move-set, our approach
    uses the unmodified move-set, addressing the additional challenge of handling
    locked configurations. Our algorithm is sequential in nature and operates with
    a worst-case time complexity of O(n^2) rounds, which is optimal for sequential
    algorithms. To improve runtime, we introduce two parallel variants of the algorithm.
    Both rely on a spanning tree data structure, allowing modules to make decisions
    based on local connectivity. Our experimental results show a significant speedup
    for the first variant, and a linear average runtime for the second variant, which
    is worst-case optimal for parallel algorithms.'
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. Invited Paper: Distributed Rhombus
    Formation of Sliding Squares. In: Bonomi S, Mandal PS, Robinson P, Sharma G, Tixeuil
    S, eds. <i>Stabilization, Safety, and Security of Distributed Systems</i>. Springer
    Nature Switzerland; 2025:325-342. doi:<a href="https://doi.org/10.1007/978-3-032-11127-2_26">10.1007/978-3-032-11127-2_26</a>'
  apa: 'Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2025). Invited Paper:
    Distributed Rhombus Formation of Sliding Squares. In S. Bonomi, P. S. Mandal,
    P. Robinson, G. Sharma, &#38; S. Tixeuil (Eds.), <i>Stabilization, Safety, and
    Security of Distributed Systems</i> (pp. 325–342). Springer Nature Switzerland.
    <a href="https://doi.org/10.1007/978-3-032-11127-2_26">https://doi.org/10.1007/978-3-032-11127-2_26</a>'
  bibtex: '@inproceedings{Kostitsyna_Liedtke_Scheideler_2025, place={Cham}, title={Invited
    Paper: Distributed Rhombus Formation of Sliding Squares}, DOI={<a href="https://doi.org/10.1007/978-3-032-11127-2_26">10.1007/978-3-032-11127-2_26</a>},
    booktitle={Stabilization, Safety, and Security of Distributed Systems}, publisher={Springer
    Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler,
    Christian}, editor={Bonomi, Silvia and Mandal, Partha Sarathi and Robinson, Peter
    and Sharma, Gokarna and Tixeuil, Sebastien}, year={2025}, pages={325–342} }'
  chicago: 'Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Invited
    Paper: Distributed Rhombus Formation of Sliding Squares.” In <i>Stabilization,
    Safety, and Security of Distributed Systems</i>, edited by Silvia Bonomi, Partha
    Sarathi Mandal, Peter Robinson, Gokarna Sharma, and Sebastien Tixeuil, 325–42.
    Cham: Springer Nature Switzerland, 2025. <a href="https://doi.org/10.1007/978-3-032-11127-2_26">https://doi.org/10.1007/978-3-032-11127-2_26</a>.'
  ieee: 'I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Invited Paper: Distributed
    Rhombus Formation of Sliding Squares,” in <i>Stabilization, Safety, and Security
    of Distributed Systems</i>, Kathmandu, 2025, pp. 325–342, doi: <a href="https://doi.org/10.1007/978-3-032-11127-2_26">10.1007/978-3-032-11127-2_26</a>.'
  mla: 'Kostitsyna, Irina, et al. “Invited Paper: Distributed Rhombus Formation of Sliding
    Squares.” <i>Stabilization, Safety, and Security of Distributed Systems</i>, edited
    by Silvia Bonomi et al., Springer Nature Switzerland, 2025, pp. 325–42, doi:<a
    href="https://doi.org/10.1007/978-3-032-11127-2_26">10.1007/978-3-032-11127-2_26</a>.'
  short: 'I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: S. Bonomi, P.S. Mandal,
    P. Robinson, G. Sharma, S. Tixeuil (Eds.), Stabilization, Safety, and Security
    of Distributed Systems, Springer Nature Switzerland, Cham, 2025, pp. 325–342.'
conference:
  end_date: 2025-10-11
  location: Kathmandu
  name: 27th International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS)
  start_date: 2025-10-09
date_created: 2025-11-23T21:07:12Z
date_updated: 2026-02-11T08:31:14Z
department:
- _id: '79'
doi: 10.1007/978-3-032-11127-2_26
editor:
- first_name: Silvia
  full_name: Bonomi, Silvia
  last_name: Bonomi
- first_name: Partha Sarathi
  full_name: Mandal, Partha Sarathi
  last_name: Mandal
- first_name: Peter
  full_name: Robinson, Peter
  last_name: Robinson
- first_name: Gokarna
  full_name: Sharma, Gokarna
  last_name: Sharma
- first_name: Sebastien
  full_name: Tixeuil, Sebastien
  last_name: Tixeuil
language:
- iso: eng
page: 325-342
place: Cham
publication: Stabilization, Safety, and Security of Distributed Systems
publication_identifier:
  isbn:
  - '9783032111265'
  - '9783032111272'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
publisher: Springer Nature Switzerland
status: public
title: 'Invited Paper: Distributed Rhombus Formation of Sliding Squares'
type: conference
user_id: '15578'
year: '2025'
...
---
_id: '62051'
article_number: '115552'
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. <i>Theoretical
    Computer Science</i>. 2025;1057. doi:<a href="https://doi.org/10.1016/j.tcs.2025.115552">10.1016/j.tcs.2025.115552</a>'
  apa: 'Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2025). Efficient shape
    formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate
    structures. <i>Theoretical Computer Science</i>, <i>1057</i>, Article 115552.
    <a href="https://doi.org/10.1016/j.tcs.2025.115552">https://doi.org/10.1016/j.tcs.2025.115552</a>'
  bibtex: '@article{Hinnenthal_Liedtke_Scheideler_2025, title={Efficient shape formation
    by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures},
    volume={1057}, DOI={<a href="https://doi.org/10.1016/j.tcs.2025.115552">10.1016/j.tcs.2025.115552</a>},
    number={115552}, journal={Theoretical Computer Science}, publisher={Elsevier BV},
    author={Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian},
    year={2025} }'
  chicago: 'Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient
    Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter
    Intermediate Structures.” <i>Theoretical Computer Science</i> 1057 (2025). <a
    href="https://doi.org/10.1016/j.tcs.2025.115552">https://doi.org/10.1016/j.tcs.2025.115552</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,”
    <i>Theoretical Computer Science</i>, vol. 1057, Art. no. 115552, 2025, doi: <a
    href="https://doi.org/10.1016/j.tcs.2025.115552">10.1016/j.tcs.2025.115552</a>.'
  mla: 'Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable
    Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>Theoretical
    Computer Science</i>, vol. 1057, 115552, Elsevier BV, 2025, doi:<a href="https://doi.org/10.1016/j.tcs.2025.115552">10.1016/j.tcs.2025.115552</a>.'
  short: K. Hinnenthal, D.J. Liedtke, C. Scheideler, Theoretical Computer Science
    1057 (2025).
date_created: 2025-11-03T10:19:53Z
date_updated: 2025-11-03T10:21:52Z
department:
- _id: '79'
doi: 10.1016/j.tcs.2025.115552
intvolume: '      1057'
language:
- iso: eng
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier BV
status: public
title: 'Efficient shape formation by 3D hybrid programmable matter: An algorithm for
  low diameter intermediate structures'
type: journal_article
user_id: '55557'
volume: 1057
year: '2025'
...
---
_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: '64104'
author:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: 'Kristian '
  full_name: 'Hinnenthal , Kristian '
  last_name: 'Hinnenthal '
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
citation:
  ama: 'Scheideler C, Hinnenthal  K, Liedtke DJ. Efficient Shape Formation by 3D Hybrid
    Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND
    2024: 15:1-15:20. In: ; 2024.'
  apa: 'Scheideler, C., Hinnenthal , K., &#38; Liedtke, D. J. (2024). <i>Efficient
    Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter
    Intermediate Structures. SAND 2024: 15:1-15:20</i>.'
  bibtex: '@inproceedings{Scheideler_Hinnenthal _Liedtke_2024, place={CoRR abs/2401.17734
    (2024)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An
    Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20}, author={Scheideler,
    Christian and Hinnenthal , Kristian  and Liedtke, David Jan}, year={2024} }'
  chicago: 'Scheideler, Christian, Kristian  Hinnenthal , and David Jan Liedtke. “Efficient
    Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter
    Intermediate Structures. SAND 2024: 15:1-15:20.” CoRR abs/2401.17734 (2024), 2024.'
  ieee: 'C. Scheideler, K. Hinnenthal , and D. J. Liedtke, “Efficient Shape Formation
    by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.
    SAND 2024: 15:1-15:20,” 2024.'
  mla: 'Scheideler, Christian, et al. <i>Efficient Shape Formation by 3D Hybrid Programmable
    Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20</i>.
    2024.'
  short: 'C. Scheideler, K. Hinnenthal , D.J. Liedtke, in: CoRR abs/2401.17734 (2024),
    2024.'
date_created: 2026-02-10T10:12:18Z
date_updated: 2026-02-11T09:12:05Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
language:
- iso: eng
place: CoRR abs/2401.17734 (2024)
status: public
title: 'Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for
  Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20'
type: conference
user_id: '15578'
year: '2024'
...
---
_id: '64106'
author:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: 'Irina '
  full_name: 'Kostitsyna, Irina '
  last_name: Kostitsyna
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
citation:
  ama: 'Scheideler C, Kostitsyna I, Liedtke DJ. Universal Coating by 3D Hybrid Programmable
    Matter. In: ; 2024.'
  apa: Scheideler, C., Kostitsyna, I., &#38; Liedtke, D. J. (2024). <i>Universal Coating
    by 3D Hybrid Programmable Matter.</i>
  bibtex: '@inproceedings{Scheideler_Kostitsyna_Liedtke_2024, place={SIROCCO 2024:
    384-401}, title={Universal Coating by 3D Hybrid Programmable Matter.}, author={Scheideler,
    Christian and Kostitsyna, Irina  and Liedtke, David Jan}, year={2024} }'
  chicago: 'Scheideler, Christian, Irina  Kostitsyna, and David Jan Liedtke. “Universal
    Coating by 3D Hybrid Programmable Matter.” SIROCCO 2024: 384-401, 2024.'
  ieee: C. Scheideler, I. Kostitsyna, and D. J. Liedtke, “Universal Coating by 3D
    Hybrid Programmable Matter.,” 2024.
  mla: Scheideler, Christian, et al. <i>Universal Coating by 3D Hybrid Programmable
    Matter.</i> 2024.
  short: 'C. Scheideler, I. Kostitsyna, D.J. Liedtke, in: SIROCCO 2024: 384-401, 2024.'
date_created: 2026-02-10T10:21:39Z
date_updated: 2026-02-11T09:12:11Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
language:
- iso: eng
place: 'SIROCCO 2024: 384-401'
status: public
title: Universal Coating by 3D Hybrid Programmable Matter.
type: conference
user_id: '15578'
year: '2024'
...
---
_id: '25126'
abstract:
- lang: eng
  text: Motivated by the prospect of computing agents that explore unknown environments
    and construct convex hulls on the nanoscale, we investigate the capabilities and
    limitations of a single deterministic finite automaton robot in the three-dimensional
    hybrid model for programmable matter. In this model, active robots move on a set
    of passive tiles, called configuration, with the geometric shape of rhombic dodecahedra
    on the adjacency graph of the face-centered cubic sphere-packing. We show that
    the exploration problem is equally hard in the hybrid model and in three-dimensional
    mazes, in which tiles have the shape of cubes and are positioned at the vertices
    of $\mathbb{Z}^3$. Thereby, a single robot with a constant number of pebbles cannot
    solve this problem in the hybrid model on arbitrary configurations. We provide
    algorithms for a robot with two pebbles that solve the exploration problem in
    the subclass of compact configurations of size $n$ in $\O(n^3)$ rounds. Further,
    we investigate the robot's capabilities of detection and hull construction in
    terms of restricted orientation convexity. We show that a robot without any pebble
    can detect strong $\O$-convexity in $\O(n)$ rounds, but cannot detect weak $\O$-convexity,
    not even if provided with a single pebble. Assuming that a robot can construct
    tiles from scratch and deconstruct previously constructed tiles, we show that
    the strong $\O$-hull of any given configuration of size $n$ can be constructed
    in $\O(n^4)$ rounds, even if the robot cannot distinguish constructed from native
    tiles.
author:
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
citation:
  ama: Liedtke DJ. <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>.; 2021.
  apa: Liedtke, D. J. (2021). <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>.
  bibtex: '@book{Liedtke_2021, title={Exploration and Convex Hull Construction in
    the Three-Dimensional Hybrid Model}, author={Liedtke, David Jan}, year={2021}
    }'
  chicago: Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the
    Three-Dimensional Hybrid Model</i>, 2021.
  ieee: D. J. Liedtke, <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>. 2021.
  mla: Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>. 2021.
  short: D.J. Liedtke, Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model, 2021.
date_created: 2021-09-29T12:37:39Z
date_updated: 2022-01-06T06:56:53Z
ddc:
- '000'
department:
- _id: '79'
file:
- access_level: local
  content_type: application/pdf
  creator: liedtke
  date_created: 2021-09-29T12:34:47Z
  date_updated: 2021-09-29T12:34:47Z
  file_id: '25128'
  file_name: Master - Thesis.pdf
  file_size: 10114825
  relation: main_file
file_date_updated: 2021-09-29T12:34:47Z
has_accepted_license: '1'
keyword:
- Robot Exploration
- Finite Automaton
- Hybrid Model for Programmable Matter
- Convex Hull
language:
- iso: eng
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model
type: mastersthesis
user_id: '55557'
year: '2021'
...
---
_id: '25121'
abstract:
- lang: eng
  text: We consider a group of $n$ autonomous mobile robots of which $m$ are stationary
    thus cannot move. Robots are represented by points in the Euclidean plane. They
    have no memory, do not communicate or share a common coordinate system and they
    move solely based on the positioning of other robots within their limited viewing
    range of 1. The goal is to gather the robots inside of the convex hull of all
    stationary robots. A variant of this problem, the general gathering problem, has
    been studied in various different time models. In this work, we consider a continuous
    time model, where robots continuously observe their neighbors, compute the next
    target of movement and move with a speed limit of 1 at any time. Regarding the
    robots' local strategy, we only study contracting algorithms in which every robot
    that is positioned on the border of the convex hull of all robots moves into this
    hull. We present a time bound of $\mathcal{O}(nd)$ for any general contracting
    algorithms in a configuration with only a single stationary robot. For configurations
    with more stationary robots, we prove that robots converge against the convex
    hull of all stationary robots and that no upper bound on the runtime exists. For
    the specific contracting algorithms Go-To-The-Left, Go-On-Bisector and Go-To-The-Middle,
    we provide linear time bounds.
author:
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
citation:
  ama: Liedtke DJ. <i>Influence of Stationary Robots on Continuous Robot Formation
    Problems</i>.; 2018.
  apa: Liedtke, D. J. (2018). <i>Influence of Stationary Robots on Continuous Robot
    Formation Problems</i>.
  bibtex: '@book{Liedtke_2018, title={Influence of Stationary Robots on Continuous
    Robot Formation Problems}, author={Liedtke, David Jan}, year={2018} }'
  chicago: Liedtke, David Jan. <i>Influence of Stationary Robots on Continuous Robot
    Formation Problems</i>, 2018.
  ieee: D. J. Liedtke, <i>Influence of Stationary Robots on Continuous Robot Formation
    Problems</i>. 2018.
  mla: Liedtke, David Jan. <i>Influence of Stationary Robots on Continuous Robot Formation
    Problems</i>. 2018.
  short: D.J. Liedtke, Influence of Stationary Robots on Continuous Robot Formation
    Problems, 2018.
date_created: 2021-09-29T12:30:40Z
date_updated: 2022-01-06T06:56:52Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: local
  content_type: application/pdf
  creator: liedtke
  date_created: 2021-09-29T12:21:24Z
  date_updated: 2021-09-29T12:21:24Z
  file_id: '25124'
  file_name: Bachelor - Thesis.pdf
  file_size: 6746519
  relation: main_file
file_date_updated: 2021-09-29T12:21:24Z
has_accepted_license: '1'
language:
- iso: eng
status: public
supervisor:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
title: Influence of Stationary Robots on Continuous Robot Formation Problems
type: bachelorsthesis
user_id: '55557'
year: '2018'
...