论文标题
关于网格中有效的具有连接性的转换
On Efficient Connectivity-Preserving Transformations in a Grid
论文作者
论文摘要
我们考虑一个位于二维正方形网格上的$ n $设备的离散系统，并形成初始连接的形状$ s_i $。每个设备都配备了线性强度机制，使其能够在一个时间步长中移动一系列连续的设备。我们通过\ emph {line moves}的有限序列研究了将$ s_i $转换为相同数量设备的给定连接的目标形状$ s_f $的问题。我们的重点是设计针对\ emph {最小化移动总数}的\ emph {集中式}转换，但要受到整个转换过程中形状的\ emph {保留连接的约束}的约束。我们首先为$ s_i $的\ emph {关联图}和$ s_f $的\ emph {关联图}提供非常快速的连接转换。特别是，我们的转换使$ o（n \ log n $）动作，渐近地等于断开连接转换的最著名的运行时间。然后，我们最一般的结果是通过一个可以通过$ O（n \ sqrt {n}）$移动的序列，可以将任何初始连接的形状$ s_i $转换为任何目标连接形状$ s_f $的任何初始连接的形状$ s_i $的结果。最后，我们为两组限制的转换集建立了$ω（n \ log n）$下限。这些是该模型的第一个下限，并且与最著名的$ O（n \ log n）$上限匹配。
We consider a discrete system of $n$ devices lying on a 2-dimensional square grid and forming an initial connected shape $S_I$. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step. We study the problem of transforming $S_I$ into a given connected target shape $S_F$ of the same number of devices, via a finite sequence of \emph{line moves}. Our focus is on designing \emph{centralised} transformations aiming at \emph{minimising the total number of moves} subject to the constraint of \emph{preserving connectivity} of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the \emph{associated graphs} of $ S_I $ and $ S_F $ are isomorphic to a Hamiltonian line. In particular, our transformations make $ O(n \log n $) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving \emph{universal transformation} that can transform any initial connected shape $ S_I $ into any target connected shape $ S_F $, through a sequence of $O(n\sqrt{n})$ moves. Finally, we establish $Ω(n \log n)$ lower bounds for two restricted sets of transformations. These are the first lower bounds for this model and are matching the best known $ O(n \log n) $ upper bounds.
