2019/04/29 by Abdullah Almethen, Almethen, Abdullah, Othon Michail +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1904.12777
openalex publication_date 2019/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study a discrete system of entities residing on a\ntwo-dimensional square grid. Each entity is modelled as a node occupying a\ndistinct cell of the grid. The set of all n nodes forms initially a connected\nshape A. Entities are equipped with a linear-strength pushing mechanism that\ncan push a whole line of entities, from 1 to n, in parallel in a single\ntime-step. A target connected shape B is also provided and the goal is to\n\transform A into B via a sequence of line movements. Existing models\nbased on local movement of individual nodes, such as rotating or sliding a\nsingle node, can be shown to be special cases of the present model, therefore\ntheir (inefficient, \Θ(n2)) \universal transformations carry over.\nOur main goal is to investigate whether the parallelism inherent in this new\ntype of movement can be exploited for efficient, i.e., sub-quadratic\nworst-case, transformations. As a first step towards this, we restrict\nattention solely to centralised transformations and leave the distributed case\nas a direction for future research. Our results are positive. By focusing on\nthe apparently hard instance of transforming a diagonal A into a straight\nline B, we first obtain transformations of time O(n\√(n)) without and\nwith preserving the connectivity of the shape throughout the transformation.\nThen, we further improve by providing two O(n\log n)-time transformations for\nthis problem. By building upon these ideas, we first manage to develop an\nO(n\√(n))-time universal transformation. Our main result is then an O(n\n\log n) -time universal transformation. We leave as an interesting open\nproblem a suspected \Ω(n\log n)-time lower bound.\n