Shortest polygonal chains covering each planar square grid

Abstract

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,\dots ,n-1\}\times \{0,1,\dots ,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).

18 pages, 13 figures; introduction improved, Kato's conjecture reformulated, and appendix moved after references