Link Length of Rectilinear Hamiltonian Tours in Grids

Abstract

The link length of a walk in a multidimensional grid is the number of straight line segments constituting the walk. Alternatively, it is the number of turns that a mobile unit needs to perform in traversing the walk. A rectilinear walk consists of straight line segments which are parallel to the main axis. We wish to construct rectilinear walks with minimal link length traversing grids. If $G$ denotes the multidimensional grid, let $s(G)$ be the minimal link length of a rectilinear walk traversing all the vertices of $G$. In this paper, we develop an asymptotically optimal algorithm for constructing rectilinear walks traversing all the vertices of complete multidimensional grids and analyze the worst-case behavior of $s(G)$, when $G$ is a multidimensional grid.