Almethen, Abdullah, Michail, Othon 
ORCID: 0000-0002-6234-3960 and Potapov, Igor
(2022)
On efficient connectivity-preserving transformations in a grid.
THEORETICAL COMPUTER SCIENCE, 898.
pp. 132-148.
|
Text
TCS20.pdf - Author Accepted Manuscript Download (1MB) | Preview |
Abstract
We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape SI. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step, called a line move. We study the problem of transforming SI into a given connected target shape SF of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of SI and SF contain a Hamiltonian path. In particular, our transformations make O(nlogn) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape SI into any target connected shape SF, through a sequence of O(nn) moves.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Line movement, Discrete transformations, Shape formation, Reconfigurable robotics, Time complexity, Programmable matter |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 09 Nov 2021 14:50 |
| Last Modified: | 18 Jan 2023 21:25 |
| DOI: | 10.1016/j.tcs.2021.11.004 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3142965 |
Dimensions
Dimensions
