Almethen, Abdullah, Michail, Othon 
ORCID: 0000-0002-6234-3960 and Potapov, Igor
(2021)
Distributed Transformations of Hamiltonian Shapes based on Line Moves.
.
|
Text
2108.08953v2.pdf - Submitted version Download (1MB) | Preview |
Abstract
We consider a discrete system of $n$ simple indistinguishable devices, called \emph{agents}, forming a \emph{connected} shape $S_I$ on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a \emph{line move}, by which an agent can push a whole line of consecutive agents in one of the four directions in a single time-step. We study the problem of transforming an initial shape $S_I$ into a given target shape $S_F$ via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. Our main contribution is the first distributed connectivity-preserving transformation that exploits line moves within a total of $O(n \log_2 n)$ moves, which is asymptotically equivalent to that of the best-known centralised transformations. The algorithm solves the \emph{line formation problem} that allows agents to form a final straight line $S_L$, starting from any shape $ S_I $, whose \emph{associated graph} contains a Hamiltonian path.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 31 pages, 18 figures |
| Uncontrolled Keywords: | cs.DS, cs.DS, cs.DC, cs.RO |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 02 Sep 2021 08:15 |
| Last Modified: | 18 Jan 2023 21:30 |
| DOI: | 10.1007/978-3-030-89240-1_1 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3135610 |
Dimensions
Dimensions
