Covering paths for planar point sets. (English) Zbl 1294.05102

Summary: Given \(n\) points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least \(n/2\) segments, and \(n-1\) straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of \(n\) points in the plane admits a (possibly self-crossing) covering path consisting of \(n/2+O(n/\log n)\) straight line segments. If the path is required to be noncrossing, we prove that \((1-{\varepsilon})n\) straight line segments suffice for a small constant \(\varepsilon > 0\), and we exhibit \(n\)-element point sets that require at least \(5n/9-O(1)\) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for \(n\) points in the plane requires \(\varOmega(n \log n)\) time in the worst case.


05C38 Paths and cycles
05C05 Trees
Full Text: DOI arXiv


[1] Aloupis, G.: A history of linear-time convex hull algorithms for simple polygons. http://cgm.cs.mcgill.ca/ athens/cs601/
[2] 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
[3] Bereg, S., Bose, P., Dumitrescu, A., Hurtado, F., Valtr, P.: Traversing a set of points with a minimum number of turns. Discrete Comput. Geom. 41(4), 513-532 (2009) · Zbl 1191.90087 · doi:10.1007/s00454-008-9127-1
[4] Brönnimann, H., Chan, T.M.: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom. 34, 75-82 (2006) · Zbl 1089.65014 · doi:10.1016/j.comgeo.2005.11.005
[5] Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485-524 (1991) · Zbl 0753.68090 · doi:10.1007/BF02574703
[6] Chvátal, V., Klincsek, G.: Finding largest convex subsets. Congr. Numer. 29, 453-460 (1980) · Zbl 0474.52004
[7] 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
[8] 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
[9] Demaine, E. D.; O’Rourke, J., Open problems from CCCG 2010, Toronto, ON
[10] Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463-470 (1935) · Zbl 0012.27010
[11] Erdős, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Bp. 3-4, 53-62 (1960-1961) · Zbl 0103.15502
[12] Estivill-Castro, V., Heednacram, A., Suraweera, F.: NP-completeness and FPT results for rectilinear covering problems. J. Univers. Comput. Sci. 15, 622-652 (2010) · Zbl 1216.68126
[13] Fulek, R., Keszegh, B., Morić, F., Uljarević, I.: On polygons excluding point sets. Graphs Comb. 29(6), 1741-1753 (2013) · Zbl 1283.05050 · doi:10.1007/s00373-012-1221-8
[14] Jiang, M., On covering points with minimum turns, No. 7285, 58-69 (2012), Berlin · Zbl 1304.68186 · doi:10.1007/978-3-642-29700-7_6
[15] Kranakis, E., Krizanc, D., Meertens, L.: Link length of rectilinear Hamiltonian tours in grids. Ars Comb. 38, 177-192 (1994) · Zbl 0816.05040
[16] Loyd, S.: Cyclopedia of Puzzles. The Lamb, Lincoln (1914)
[17] Matoušek, J.: Lectures on Discrete Geometry. Springer, New York (2002) · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7
[18] Melkman, A.: On-line construction of the convex hull of a simple polygon. Inf. Process. Lett. 25(1), 11-12 (1987) · Zbl 0653.68028 · doi:10.1016/0020-0190(87)90086-X
[19] Mitchell, J. S.B.; Sack, J.-R. (ed.); Urrutia, J. (ed.), Geometric shortest paths and network optimization, 633-701 (2000), Amsterdam · Zbl 0941.68137 · doi:10.1016/B978-044482537-7/50016-4
[20] Morić, F.: In: Separating and Covering Points in the Plane, Communication at the Open Problem Session, 22nd Canadian Conf. Comput. Geom., Winnipeg, MB (2010)
[21] Morić, F., Covering points by a polygonal line, Wergenstein, Switzerland
[22] Preparata, F.P., Shamos, M.I.: Computational Geometry: an Introduction. Springer, New York (1985) · Zbl 0575.68059 · doi:10.1007/978-1-4612-1098-6
[23] Stein, C.; Wagner, D. P., Approximation algorithms for the minimum bends traveling salesman problem, No. 2081, 406-421 (2001) · Zbl 1010.90519
[24] Welzl, E.: In: Communication at the 9th Gremo’s Workshop on Open Problems, Wergenstein, Switzerland (2011)
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.