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