On efficient connectivity-preserving transformations in a grid

DOI10.1007/978-3-030-62401-9_6zbMath1475.68387arXiv2005.08351OpenAlexW3107690891MaRDI QIDQ5918321

Othon Michail, Igor Potapov, Abdullah Almethen

Publication date: 8 July 2021

Published in: Theoretical Computer Science, Algorithms for Sensor Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.08351

zbMATH Keywords

time complexityprogrammable matterdiscrete transformationsshape formationreconfigurable roboticsline movement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15) Other nonclassical models of computation (68Q09)

Related Items (2)

On efficient connectivity-preserving transformations in a grid ⋮ Distributed transformations of Hamiltonian shapes based on line moves

Uses Software

• CADbots

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizing geometric patterns formable by oblivious anonymous mobile robots
• On the transformation capability of feasible mechanisms for programmable matter
• The computational power of population protocols
• Pushing lines helps: efficient universal centralised transformations for programmable matter
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata
• Forming sequences of geometric patterns with oblivious mobile robots
• Computation in networks of passively mobile finite-state sensors
• On the bounded-hop MST problem on random Euclidean instances
• Efficient reconfiguration of lattice-based modular robots
• On the Runtime of Universal Coating for Programmable Matter
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Distributed Computing by Mobile Robots: Gathering
• The program-size complexity of self-assembled squares (extended abstract)
• Shape formation by programmable particles
• Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves
• Hamilton Paths in Grid Graphs
• Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
• Distributed reconfiguration of metamorphic robot chains
• Pushing squares around
• Brief Announcement
• Simple and efficient local codes for distributed stable network construction
• On efficient connectivity-preserving transformations in a grid

This page was built for publication: On efficient connectivity-preserving transformations in a grid