Connor, Matthew and Michail, Othon 
ORCID: 0000-0002-6234-3960
(2022)
Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for All Orthogonal Convex Shapes.
In: International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS).
|
Text
2207.03062.pdf - Author Accepted Manuscript Download (5MB) | Preview |
Abstract
We study a model of programmable matter systems consisting of n devices lying on the cells of a 2-dimensional square grid, which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape of devices A into a target shape B. We are interested in characterising the class of shapes which can be transformed into each other in such a scenario, under the additional constraint of maintaining global connectivity at all times. This was one of the main problems left open by [Michail et al., JCSS’19]. Note that the considered question is about structural feasibility of transformations, which we exclusively deal with via centralised constructive proofs. Distributed solutions are left for future work and form an interesting research direction. Past work made some progress for the special class of colour-consistent nice shapes. We here consider the class of orthogonal convex shapes, where for any two nodes u, v in a horizontal or vertical line on the grid, there is no empty cell between u and v. We develop a generic centralised transformation and prove that, for any pair A, B of colour-consistent orthogonal convex shapes, it can transform A into B. In light of the existence of blocked shapes in the considered class, we use a minimal 3-node seed (additional nodes placed at the start) to trigger the transformation. The running time of our transformation is an optimal sequential moves, where. We leave as an open problem the existence of a universal connectivity-preserving transformation with a small seed. Our belief is that the techniques developed in this paper might prove useful to answer this.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Aug 2022 08:02 |
| Last Modified: | 18 Jan 2023 20:53 |
| DOI: | 10.1007/978-3-031-22050-0_5 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3160446 |
Dimensions
Dimensions
