[{"title":"Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model","date_updated":"2022-01-06T06:56:53Z","supervisor":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"}],"author":[{"first_name":"David Jan","id":"55557","full_name":"Liedtke, David Jan","last_name":"Liedtke"}],"date_created":"2021-09-29T12:37:39Z","year":"2021","citation":{"short":"D.J. Liedtke, Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model, 2021.","bibtex":"@book{Liedtke_2021, title={Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model}, author={Liedtke, David Jan}, year={2021} }","mla":"Liedtke, David Jan. <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>.","ama":"Liedtke DJ. <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.","chicago":"Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>, 2021."},"has_accepted_license":"1","ddc":["000"],"keyword":["Robot Exploration","Finite Automaton","Hybrid Model for Programmable Matter","Convex Hull"],"file_date_updated":"2021-09-29T12:34:47Z","language":[{"iso":"eng"}],"_id":"25126","user_id":"55557","department":[{"_id":"79"}],"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."}],"file":[{"content_type":"application/pdf","relation":"main_file","date_updated":"2021-09-29T12:34:47Z","date_created":"2021-09-29T12:34:47Z","creator":"liedtke","file_size":10114825,"file_name":"Master - Thesis.pdf","access_level":"local","file_id":"25128"}],"status":"public","type":"mastersthesis"}]