Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model Liedtke, David Jan Robot Exploration Finite Automaton Hybrid Model for Programmable Matter Convex Hull ddc:000 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. 2021 info:eu-repo/semantics/other doc-type:other text http://purl.org/coar/resource_type/c_1843 https://ris.uni-paderborn.de/record/25126 Liedtke DJ. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>.; 2021. eng info:eu-repo/semantics/restrictedAccess