Almethen, Abdullah, Michail, Othon 
ORCID: 0000-0002-6234-3960 and Potapov, Igor
(2019)
Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter.
[Internet Publication]
|
Text
1904.12777v1.pdf - Submitted version Download (2MB) | Preview |
Abstract
In this paper, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all $n$ nodes forms initially a connected shape $A$. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities, from 1 to $n$, in parallel in a single time-step. A target connected shape $B$ is also provided and the goal is to \emph{transform} $A$ into $B$ via a sequence of line movements. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, $\Theta(n^2)$) \emph{universal transformations} carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i.e., sub-quadratic worst-case, transformations. As a first step towards this, we restrict attention solely to centralised transformations and leave the distributed case as a direction for future research. Our results are positive. By focusing on the apparently hard instance of transforming a diagonal $A$ into a straight line $B$, we first obtain transformations of time $O(n\sqrt{n})$ without and with preserving the connectivity of the shape throughout the transformation. Then, we further improve by providing two $O(n\log n)$-time transformations for this problem. By building upon these ideas, we first manage to develop an $O(n\sqrt{n})$-time universal transformation. Our main result is then an $ O(n \log n) $-time universal transformation. We leave as an interesting open problem a suspected $\Omega(n\log n)$-time lower bound.
| Item Type: | Internet Publication |
|---|---|
| Additional Information: | 40 pages, 27 figures |
| Uncontrolled Keywords: | cs.DS, cs.DS, cs.RO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 30 Sep 2019 14:15 |
| Last Modified: | 19 Jan 2023 00:25 |
| DOI: | 10.1007/978-3-030-34405-4_3 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3056454 |
Dimensions
Dimensions
