Fort Formation by an Automaton
| Autor: | Partha Sarathi Mandal, Kartikey Kant, Debasish Pattanayak |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Square tiling
FOS: Computer and information sciences Brick Computer science Geometry 0102 computer and information sciences Computational Complexity (cs.CC) Span (engineering) Grid 01 natural sciences Upper and lower bounds 03 medical and health sciences Computer Science - Computational Complexity 0302 clinical medicine Deterministic finite automaton 010201 computation theory & mathematics 030220 oncology & carcinogenesis Point (geometry) Rectangle Computer Science::Distributed Parallel and Cluster Computing |
| Zdroj: | COMSNETS |
| DOI: | 10.48550/arxiv.2011.15074 |
| Popis: | Building structures by low capability robots is a very recent research development. A robot (or a mobile agent) is designed as a deterministic finite automaton. The objective is to make a structure from a given distribution of materials (\textit{bricks}) in an infinite grid $Z\times Z$. The grid cells may contain a brick (\textit{full cells}) or it may be empty (\textit{empty cells}). The \textit{field}, a sub-graph induced by the full cells, is initially connected. At a given point in time, a robot can carry at most one brick. The robot can move in four directions (north, east, south, and west) and starts from a \textit{full cell}. The \textit{Manhattan distance} between the farthest full cells is the \textit{span} of the field. We consider the construction of a \textit{fort}, a structure with the minimum span and maximum covered area. On a square grid, a fort is a hollow rectangle with bricks on the perimeter. We show that the construction of such a fort can be done in $O(z^2)$ time -- with a matching lower bound $\Omega(z^2)$ -- where $z$ is the number of bricks present in the environment. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|