@inproceedings{54807,
  abstract     = {{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.}},
  author       = {{Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian}},
  booktitle    = {{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}},
  editor       = {{Casteigts, Arnaud and Kuhn, Fabian}},
  isbn         = {{978-3-95977-315-7}},
  issn         = {{1868-8969}},
  keywords     = {{Programmable Matter, Shape Formation, 3D Model, Finite Automaton}},
  pages        = {{15:1–15:20}},
  publisher    = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}},
  title        = {{{Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures}}},
  doi          = {{10.4230/LIPIcs.SAND.2024.15}},
  volume       = {{292}},
  year         = {{2024}},
}

@inbook{54802,
  abstract     = {{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       = {{Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}},
  booktitle    = {{Structural Information and Communication Complexity}},
  editor       = {{Emek, Yuval}},
  isbn         = {{9783031606021}},
  issn         = {{0302-9743}},
  keywords     = {{Programmable Matter, Coating, Finite Automaton, 3D}},
  publisher    = {{Springer Nature Switzerland}},
  title        = {{{Universal Coating by 3D Hybrid Programmable Matter}}},
  doi          = {{10.1007/978-3-031-60603-8_21}},
  year         = {{2024}},
}

@misc{25126,
  abstract     = {{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       = {{Liedtke, David Jan}},
  keywords     = {{Robot Exploration, Finite Automaton, Hybrid Model for Programmable Matter, Convex Hull}},
  title        = {{{Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model}}},
  year         = {{2021}},
}