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 … Read more