Link length of rectilinear Hamiltonian tours in grids
Lambert Meertens, Danny Kriz̧anc, Evangelos Kranakis · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1994
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.