20090601
Traversing a set of points with a minimum number of turns
Publication
Publication
Discrete and Computational Geometry , Volume 41  Issue 4 p. 513 532
Given a finite set of points S in ℝ d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has 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 axisaligned. Let L(S) be the minimum number of links of an axisaligned path for S, and let G n d be an n × ×n grid in ℤd . Kranakis et al. (Ars Comb. 38:177192, 1994) showed that L(G n 2 )=2n1 and L(Gn 2) = 2n 1 and 4/3n2 O(n) ≤ L(Gn 3) ≤ 3/2n2 + O(n) and conjectured that, for all d ≥ 3, L(Gnd>=d/d1 nd1 ± O(nd2) We prove the conjecture for d=3 by showing the lower bound for L(G n 3 ). For d=4, we prove that L(G n 4) = 4/3n2 ± O(n5/2). For general d, we give new estimates on L(G n d ) that are very close to the conjectured value. The new lower bound of (1 + 1/d1)n d1  O(nd2) improves previous result by Collins and Moret (Inf. Process. Lett. 68:317319, 1998), while the new upper bound of (1 + 1/d1)nd1  O(nd3/2) differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axisaligned path traversing any planar npoint set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝd with an axisaligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm.
Additional Metadata  

Approximation algorithms, Computational geometry, Minimum link spanning path  
dx.doi.org/10.1007/s0045400891271  
Discrete and Computational Geometry  
Organisation  School of Computer Science 
Bereg, S. (Sergey), Bose, P, Dumitrescu, A. (Adrian), Hurtado, F. (Ferran), & Valtr, P. (Pavel). (2009). Traversing a set of points with a minimum number of turns. Discrete and Computational Geometry, 41(4), 513–532. doi:10.1007/s0045400891271
