论文标题
关于通过增长操作的几何形状结构
On Geometric Shape Construction via Growth Operations
论文作者
论文摘要
在这项工作中，我们研究了新型算法生长过程。特别是，我们提出了三个增长操作，全倍加倍，加倍和加倍，并探索其在几何环境下所得过程的算法和结构特性。在建模方面，我们的系统在二维网格上运行，并以离散的时间段运行。该过程以初始形状$ s_i = s_0 $开头，并且在每个时间段$ t \ geq 1 $中，通过（并行）对当前形状$ s_ {t-1} $应用（并行）一个或多个增长类型的一个或多个增长操作，生成下一个实例$ s_t $ > | s_ {t-1} | $。我们的目标是表征可以在$ o（\ log n）$或Polylog $ n $ time步骤中构建的形状类别，并确定最终形状$ s_f $是否可以使用给定类型的有限增长操作（称为constructors of $ s_f $ $ s_f $）从初始形状$ s_i $构建。 对于完整的加倍，在每个时间阶段，每个节点都会在给定方向上生成一个新节点，我们完全表征可以从给定初始形状构造的形状类别的结构。对于RC加倍（在完整的列或行双倍）中，我们的主要贡献是一种线性的集中算法，对于任何一对形状$ s_i $，$ s_f $决定是否可以从$ s_i $中构建$ s_f $，如果答案是YES是$ O（\ log N）$ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s_ $ s $ os s $ os s $。对于最一般的加倍操作（在单个节点上可以加倍），我们表明某些形状不能以次线性时间阶段构建，并从单粒$ s_i $中给出两个$ s_f $的通用构造函数，这些$ s_i $有效（即，对于大型形状类别）。两个构造函数都可以通过多项式时间集中算法计算出任何形状$ s_f $。
In this work, we investigate novel algorithmic growth processes. In particular, we propose three growth operations, full doubling, RC doubling and doubling, and explore the algorithmic and structural properties of their resulting processes under a geometric setting. In terms of modeling, our system runs on a 2-dimensional grid and operates in discrete time-steps. The process begins with an initial shape $S_I=S_0$ and, in every time-step $t \geq 1$, by applying (in parallel) one or more growth operations of a specific type to the current shape-instance $S_{t-1}$, generates the next instance $S_t$, always satisfying $|S_t| > |S_{t-1}|$. Our goal is to characterize the classes of shapes that can be constructed in $O(\log n)$ or polylog $n$ time-steps and determine whether a final shape $S_F$ can be constructed from an initial shape $S_I$ using a finite sequence of growth operations of a given type, called a constructor of $S_F$. For full doubling, in which, in every time-step, every node generates a new node in a given direction, we completely characterize the structure of the class of shapes that can be constructed from a given initial shape. For RC doubling, in which complete columns or rows double, our main contribution is a linear-time centralized algorithm that for any pair of shapes $S_I$, $S_F$ decides if $S_F$ can be constructed from $S_I$ and, if the answer is yes, returns an $O(\log n)$-time-step constructor of $S_F$ from $S_I$. For the most general doubling operation, where up to individual nodes can double, we show that some shapes cannot be constructed in sub-linear time-steps and give two universal constructors of any $S_F$ from a singleton $S_I$, which are efficient (i.e., up to polylogarithmic time-steps) for large classes of shapes. Both constructors can be computed by polynomial-time centralized algorithms for any shape $S_F$.
