• COVERING PATHS IN HYPERCUBES: CONJECTURE ABOUT LINK LENGTH BOUNDED FROM BELOW

Abstract

In 1994 Kranakis et al. published a conjecture about the minimal length of a rectilinear (polygonal) covering path in a k-dimensional n × ... × n points grid. In this paper we consider the general Line-Cover problem, where the line-segments are not required to be axis-parallel, showing that, given n = 3 < k, the known lower bound is not greater than the upper bound of the original Kranakis’ conjecture only if exists a multiplicative constant c ≥ 1.5 for the lower order terms.