Universal Coating by 3D Hybrid Programmable Matter
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910327924326400 |
|---|---|
| author | Kostitsyna, Irina Liedtke, David Scheideler, Christian |
| author_facet | Kostitsyna, Irina Liedtke, David Scheideler, Christian |
| contents | 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 $\mathcal{O}(n^2)$ steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_16180 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Universal Coating by 3D Hybrid Programmable Matter Kostitsyna, Irina Liedtke, David Scheideler, Christian Data Structures and Algorithms Emerging Technologies 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 $\mathcal{O}(n^2)$ steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions. |
| title | Universal Coating by 3D Hybrid Programmable Matter |
| topic | Data Structures and Algorithms Emerging Technologies |
| url | https://arxiv.org/abs/2303.16180 |