English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study a model of programmable matter systems consisting of $n$ deviceslying on a 2-dimensional square grid, which are able to perform the minimalmechanical operation of rotating around each other. The goal is to transform aninitial shape A into a target shape B. We are interested in characterising theclass of shapes which can be transformed into each other in such a scenario,under the additional constraint of maintaining global connectivity at alltimes. This was one of the main problems left open by $[$Michail et al.,JCSS'19$]$. Note that the considered question is about structural feasibilityof transformations, which we exclusively deal with via centralised constructiveproofs. Distributed solutions are left for future work and form an interestingresearch direction. Past work made some progress for the special class of niceshapes. We here consider the class of orthogonal convex shapes, where for anytwo nodes $u, v$ in a horizontal or vertical line on the grid, there is noempty cell between $u$ and $v$. We develop a generic centralised transformationand prove that, for any pair $A$, $B$ of colour-consistent orthogonal convexshapes, it can transform $A$ into $B$. In light of the existence of blockedshapes in the considered class, we use a minimal 3-node seed to trigger thetransformation. The running time of our transformation is an optimal $O(n^2)$sequential moves, where $n=|A|=|B|$. We leave as an open problem the existenceof a universal connectivity-preserving transformation with a small seed. Ourbelief is that the techniques developed in this paper might prove useful toanswer this.

Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for all Orthogonal Convex Shapes