---
_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'
...