Traversing a set of points with a minimum number of turns. (English) Zbl 1191.90087

Summary: Given a finite set of points \(S\) in \(\mathbb R^{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 axis-aligned. Let \(L(S)\) be the minimum number of links of an axis-aligned path for \(S\), and let \(G\) be an \(n \times \cdots \times n\) grid in \(\mathbb Z^{d}\). E. Kranakis, D. Krizanc and L. Meertens [Ars Comb. 38, 177–192 (1994; Zbl 0816.05040)] showed that \(L(G^2_n) = 2n - 1\) and \(\frac{4}{3}n^{2}-O(n)\leq L(G^{3}_{n})\leq \frac{3}{2}n^{2}+O(n)\) and conjectured that, for all \(d\geq 3, L(G^{d}_{n})=\frac{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})=\frac{4}{3}n^{3}\pm O(n^{5/2}).\)
For general \(d\), we give new estimates on \(L(G^d_n)\) that are very close to the conjectured value. The new lower bound of \((1+\frac{1}{d})n^{d-1}-O(n^{d-2})\) improves previous result by M. J. Collins and M. F. Moret [Inf. Process. Lett. 68, 317–319 (1998)], while the new upper bound of \((1+\frac{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 include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar \(n\)-point 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 \(\mathbb R^{d }\) with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension \(d\)) approximation algorithm.


90C35 Programming involving graphs or networks
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)


Zbl 0816.05040
Full Text: DOI


[1] Arkin, E.M., Mitchell, J.S.B., Piatko, C.D.: Minimum-link watchman tours. Inf. Process. Lett. 86, 203-207 (2003) · Zbl 1173.68757 · doi:10.1016/S0020-0190(02)00502-1
[2] Arkin, E.M., Bender, M.A., Demaine, E.D., Fekete, S.P., Mitchell, J.S.B., Sethia, S.: Optimal covering tours with turn costs. SIAM J. Comput. 35(3), 531-566 (2005) · Zbl 1122.90064 · doi:10.1137/S0097539703434267
[3] Braß, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005) · Zbl 1086.52001
[4] Collins, M.J.: Covering a set of points with a minimum number of turns. Int. J. Comput. Geom. Appl. 14(1-2), 105-114 (2004) · Zbl 1077.68069 · doi:10.1142/S021819590400138X
[5] Collins, M.J., Moret, M.E.: Improved lower bounds for the link length of rectilinear spanning paths in grids. Inf. Process. Lett. 68, 317-319 (1998) · Zbl 1339.68203 · doi:10.1016/S0020-0190(98)00178-1
[6] Fekete, S.P., Woeginger, G.J.: Angle-restricted tours in the plane. Comput. Geom.: Theory Appl. 8(4), 195-218 (1997) · Zbl 1133.90385
[7] Gaur, D.R., Bhattacharya, B.: Covering points by axis parallel lines. In: Proc. 23rd European Workshop on Computational Geometry, pp. 42-45 (2007)
[8] Gavril, F.: Some NP-complete problems on graphs. In: Proc. 11th Conference on Information Sciences and Systems, pp. 91-95 (1977)
[9] Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines. Discrete Appl. Math. 30(1), 29-42 (1991) · Zbl 0800.68619 · doi:10.1016/0166-218X(91)90011-K
[10] Kranakis, E., Krizanc, D., Meertens, L.: Link length of rectilinear Hamiltonian tours in grids. Ars Comb. 38, 177-192 (1994) · Zbl 0816.05040
[11] Maheshwari, A.; Sack, J.-R.; Djidjev, H. N.; Sack, J.-R. (ed.); Urrutia, J. (ed.), Link distance problems, 519-558 (2000), Amsterdam · Zbl 0953.68138 · doi:10.1016/B978-044482537-7/50013-9
[12] Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1(5), 194-197 (1982) · Zbl 0507.90025 · doi:10.1016/0167-6377(82)90039-6
[13] Stein, C.; Wagner, D. P., Approximation algorithms for the minimum bends traveling salesman problem, No. 2081, 406-421 (2001), Berlin · Zbl 1010.90519
[14] Wagner, D.P.: Path planning algorithms under the link-distance metric. Ph.D. thesis, Dartmouth College (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.