Given a finite set of points S in R^d, consider visiting the points in S with a
polygonal path which makes a minimum number of turns, or equivalently, has the
the minimum number of segments (links). We call this minimization problem the
*minimum link spanning path* problem. This natural problem has appeared
several times in the literature under different variants. The simplest one is
that in which the allowed paths are axis-aligned. Let L(S) be the minimum
number of links of an axis-aligned path for S and let G^d_n be a n x ... x n
grid in Z^d. It is known that L(G^2_n) = 2n-1 and 4/3 n^2 - O(n) <= L(G^2_n) <=
3/2 n^2 + O(n). Kranakis et al. conjectured that, for all d >= 3,
L(G^d_n) = d/(d-1)n^{d-1}\pm O(n^{d-2}). We prove the conjecture for d = 3 by
showing the lower bound for L(G^3_n). For d = 4, we prove that L(G^4_n) = 4/3 n^3
\pm O(n^{5/2}).

For general d, we give new estimates on L(G^d_n), that bring us
very close to the conjectured value. The new lower bound
(1+1/d)n^{d-1} - O(n^{d-2})
improves previous result by Collins and Moret, while the new upper bound
(1+1/(d-1))n^{d-1} + O(n^{d-3/2}) differs from the
conjectured value only in the lower order terms.

For arbitrary point sets, we give a an exact bound on the minimum number of
links needed in an axis-aligned path in traversing any planar n-point set. We
also obtain similar tight estimates (within 1) in any number of dimensions d.
For the general problem of traversing an arbitrary set of points in R^d by
an axis-aligned spanning path with a minimum number of links, we present a
constant ratio (depending on the dimension d) approximation algorithm.

This is joint work with Sergey Bereg, Jit Bose, Ferran Hurtado, and Pavel Valtr