Almethen, Abdullah, Michail, O 
ORCID: 0000-0002-6234-3960 and Potapov, I
(2019)
Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter.
In: International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS).
|
Text
AMP-ALGOSENSORS19.pdf - Author Accepted Manuscript Download (699kB) | Preview |
Abstract
In this work, 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 in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape B is also provided and the goal is to transform A into B via a sequence of line moves. 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, Θ(n2)-time) 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. This paper provides several solutions for specific and universal centralised transformations in the context of the new model. In particular we first design O(nlogn)-time universal transformation without preserving the connectivity of original shape. Then we focus on transformations which preserve the connectivity of the shape throughout its course and develop an O(nn)-time transformation for the apparently hard instance of transforming a diagonal A into a straight line B.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | Programmable matter, Transformation, Reconfigurable robotics, Shape formation, Complexity, Distributed algorithms |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Sep 2019 08:36 |
| Last Modified: | 19 Jan 2023 00:26 |
| DOI: | 10.1007/978-3-030-34405-4_3 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3054746 |
Dimensions
Dimensions
