Citation
Inspired by some preliminary results originally published in 2019 on IJMA, 10(8), pp. 36-38.
Minimum-Link Covering Trails for any Hypercubic Lattice
\(\)
In 1994, Kranakis et al. published a conjecture about the minimum link-length of every rectilinear covering path for the \(k\)-dimensional grid \(P(n,k) := \{0,1, \dots, n-1\} \times \{0,1, \dots, n-1\} \times \cdots \times \{0,1, \dots, n-1\}\). In this paper we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be axis-parallel, showing that the original Theorem 1 by Kranakis et al. no longer holds when the aforementioned constraint is disregarded. Furthermore, for any given \(n\) above two, as \(k\) approaches infinity, the link-length of any minimal (non-rectilinear) polygonal chain does not exceed Kranakis’ conjectured value of \(\frac{k}{k-1} \cdot n^{k-1}+O(n^{k-2})\) only if we introduce a multiplicative constant \(c \geq 1.5\) for the lower order terms (e.g., if we select \(n=3\) and assume that \(c<1.5\), starting from a sufficiently large \(k\), it is not possible to visit all the nodes of \(P(n,k)\) with a trail of link-length \(\frac{k}{k-1} \cdot n^{k-1}+c \cdot n^{k-2}\)).