Traversing a set of points with a minimum number of turns

ABSTRACT

Given a finite set of points S in R^d, consider visiting thepoints in S with a polygonal path that makes a minimum number ofturns, or equivalently, has the the minimum number of segments(links). We call this minimization problem the minimum linkspanning path problem. This natural problem has appeared severaltimes in the literature under different variants. The simplest oneis where the allowed paths are axis-aligned. Let L(S) be theminimum number of links of an axis-aligned path for S denote by G^d_n the d-dimensional grid of size n. Kranakis, Krizanc andMeertens (Ars Combinatoria, vol. 38, pp. 177--192, 1994)showed that in 2-dimensions L(G²_n)=2n-1 and in three dimensions 4/3 n²-O(n)< L(G³_n) < 3/2 n²+O(n). Kranakiset al. conjectured that, for all d ≥ 3, L(G^d_n)= d/d-1 n^d-1 ± O(n^d-2). We prove theconjecture for d=3 by showing that L(G³_n) ≥ 3/2 n² -O(n). For d=4, we prove that 4/3 n³ -O(n²) ≤ L(G⁴_n) ≤ 4/3 n³ +O(n^5/2).For general d, we give new estimates on L(G^d_n), that bring usvery close to the conjectured value. The new lower bound of (1+ 1/d)n^d-1-O(n^d-2) improves previous result byCollins and Moret (Information Processing Letters, vol. 68,pp. 317--319, 1998), while the new upper bound of (1+ 1/d-1)n^d-1+O(n^d-3/2) differs from the conjecturedvalue only in the lower order terms. For arbitrary point sets, we give an exact bound on the minimumnumber of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in anynumber of dimensions d. For the general problem of traversing anarbitrary set of points in R^d with an axis-aligned spanning pathhaving a minimum number of links, we present a constant ratio(depending on the dimension d) approximation algorithm.

REFERENCES

• 1: Esther M. Arkin , Michael A. Bender , Erik D. Demaine , Sándor P. Fekete , Joseph S. B. Mitchell , Saurabh Sethia, Optimal Covering Tours with Turn Costs, SIAM Journal on Computing, v.35 n.3, p.531-566, 2005 [doi>10.1137/S0097539703434267]
• 2: Esther M. Arkin , Joseph S. B. Mitchell , Christine D. Piatko, Minimum-link watchman tours, Information Processing Letters, v.86 n.4, p.203-207, 31 May 2003 [doi>10.1016/S0020-0190(02)00502-1]
• 3: P. Bras , W. Moser, and J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005.
• 4: Michael J. Collins , Bernard M. E. Moret, Improved lower bounds for the link length of rectilinear spanning paths in grids, Information Processing Letters, v.68 n.6, p.317-319, Dec 1998 [doi>10.1016/S0020-0190(98)00178-1]
• 5: M. J. Collins, Covering a set of points with a minimum number of turns, International Journal of Computational Geometry & Applications, 14(1--2) (2004), 105--114.
• 6: Sándor P. Fekete , Gerhard J. Woeginger, Angle-restricted tours in the plane, Computational Geometry: Theory and Applications, v.8 n.4, p.195-218, Sept. 1997 [doi>10.1016/S0925-7721(96)00012-0]
• 7: F. Gavril, Some NP-complete problems on graphs, Proc. 11th Conference on Information Sciences and Systems, 1977, 91--95.
• 8: Refael Hassin , Nimrod Megiddo, Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics, v.30 n.1, p.29-42, Jan. 7, 1991 [doi>10.1016/0166-218X(91)90011-K]
• 9: E. Kranakis, D. Krizanc and L. Meertens, Link length of rectilinear Hamiltonian tours in grids, Ars Combinatoria, 38 (1994), 177--192.
• 10: A. Maheshwari, J-R. Sack and H.N. Djidjev, Link distance problems, in Handbook of Computational Geometry (J-R. Sack and J. Urrutia, eds.), chap12, Elsevier, 2000, pp519--558.
• 11: N. Megiddo and A. Tamir, On the complexity of locating linear facilities in the plane, Operations Research Letters, 1(5) (1982), 194--197.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms

Keywords:
approximation algorithms, computational geometry, minimum link spanning path