Link Length of Rectilinear Hamiltonian Tours in Grids

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.