Minimum-Link Covering Trails for any Hypercubic Lattice

In 1994, Kranakis et al. published a conjecture about the minimum link-length of any rectilinear covering path for the k-dimensional grid P(n,k) := {0,1,...,n-1} × {0,1,...,n-1} × ... × {0,1,...,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. does not hold anymore 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 (k/(k-1))⋅n^(k-1)+O(n^(k-2)) only if we introduce a multiplicative constant c≥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 (k/(k-1))⋅n^(k-1)+c⋅(n^(k-2)).


Inspired by some preliminary results originally published in 2019 on IJMA, 10(8), pp. 36-38.



View Minimum-Link Covering Trails for any Hypercubic Lattice