论文标题
覆盖每个平面正方形网格的最短多边形链
Shortest polygonal chains covering each planar square grid
论文作者
论文摘要
Given any $n \in \mathbb{Z}^{+}$, we constructively prove the existence of covering paths and circuits in the plane which are characterized by the same link length of the minimum-link covering trails for the two-dimensional grid $G_n^2 := \{0,1, \ldots, n-1\} \times \{0, 1, \ldots, N-1 \} $。此外，我们推出了一种一般算法，该算法返回一个均匀值$ n $的类似链路长度的覆盖周期。最后，我们提供紧密的上限$ n^2-3 + 5 \ cdot \ sqrt {2} $单位，用于访问所有$ g_n^2 $的最小总距离，并带有最低链路径径（即，如果$ 2 \ cdot n -2 $ edges two $ n $ n.y $ n $ naugy two $ n $ aft两者都超过$ n -2 $ edges（即，$ 2 \ cdot n -2 $ edge）。
Given any $n \in \mathbb{Z}^{+}$, we constructively prove the existence of covering paths and circuits in the plane which are characterized by the same link length of the minimum-link covering trails for the two-dimensional grid $G_n^2 := \{0,1, \ldots, n-1\} \times \{0, 1, \ldots, n-1\}$. Furthermore, we introduce a general algorithm that returns a covering cycle of analogous link length for any even value of $n$. Finally, we provide the tight upper bound $n^2 - 3 + 5 \cdot \sqrt{2}$ units for the minimum total distance travelled to visit all the nodes of $G_n^2$ with a minimum-link trail (i.e., a trail with $2 \cdot n - 2$ edges if $n$ is above two).
