MIT Combinatorics Seminar

Traversing a set of points with a minimum number of turns

Adrian Dumitrescu  (University of Wisconsin-Milwaukee)

Wednesday, March 21, 2007    4:15 pm    Room 2-136


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