---
res:
  bibo_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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: David Jan
      foaf_name: Liedtke, David Jan
      foaf_surname: Liedtke
      foaf_workInfoHomepage: http://www.librecat.org/personId=55557
  dct_date: 2021^xs_gYear
  dct_language: eng
  dct_subject:
  - Robot Exploration
  - Finite Automaton
  - Hybrid Model for Programmable Matter
  - Convex Hull
  dct_title: Exploration and Convex Hull Construction in the Three-Dimensional Hybrid
    Model@
...