2022/06/22 by Marco Ripà, Ripà, Marco
Computer Science · Engineering · #05C38 #05C57 #Computational Geometry and Mesh Generation #FOS: Mathematics #General Mathematics (math.GM) #Interconnection Networks and Systems #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2208.01699
openalex publication_date 2022/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, …, 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. no longer holds when the aforementioned constraint is disregarded. Furthermore, for any n greater than 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) ⋅ nk-1+O(nk-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) ⋅ nk-1+c ⋅ nk-2).