×

On the approximability of covering points by lines and related problems. (English) Zbl 1335.65029

The authors study the computational complexity of several different problems. The first studied problem is the covering points by lines problem, i.e., given a set \(P\) of \(n\) points in the plane find a minimum-cardinality set \(L\) of lines such that every point \(p \in P\) is in some line \(l \in L\). They prove that the approximation ratio of the greedy algorithm for solving this problem is \(\Omega(\log n)\) and that the problem is APX-hard. Next, they study the maximum point coverage by lines problem, i.e., given a set \(P\) of \(n\) points in the plane and a number \(k\) find \(k\) lines that cover the maximum number of points in \(P\). Also, in this case, they prove that the problem is APX-hard. Then, they prove that the minimum-link covering tour problem is APX-hard and that the minimum-link spanning tour is NP-hard. The minimum-link covering tour (minimum-link spanning tour) problem is a problem in which for a given set \(P\) of \(n\) points in the plane we look for the covering tour (spanning tour) with the minimum number of link (segments). Finally, the authors study the min-max-turn Hamiltonian tour problem and the bounded-turn-minimum-length Hamiltonian tour problem. In the first problem for a given \(n\) points in the plane we search for a Hamiltonian tour that minimizes the maximum turning angle, whereas in the second problem for given \(n\) points in the plane and an angle \(\alpha \in [0, \pi]\), we search for a Hamiltonian tour with each turning angle at most \(\alpha\), if it exists, that has the minimum length. They prove that the min-max-turn Hamiltonian tour problem is APX-hard and the bounded-turn-minimum-length Hamiltonian tour problem is NP-hard.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aggarwal, A.; Coppersmith, D.; Khanna, S.; Motwani, R.; Schieber, B., The angular-metric traveling salesman problem, SIAM J. Comput.. (Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’97 (1997)), 29, 221-229 (1999), an extended abstract · Zbl 1321.68293
[2] Agarwal, P. K.; Raghavan, P.; Tamaki, H., Motion planning for a steering-constrained robot through moderate obstacles, (Proceedings of the 27th Annual ACM Symposium on Theory of Computing. Proceedings of the 27th Annual ACM Symposium on Theory of Computing, STOC’95 (1995)), 343-352 · Zbl 0925.93669
[3] Alon, N., A non-linear lower bound for planar epsilon-nets, Discrete Comput. Geom., 47, 235-244 (2012) · Zbl 1232.68161
[4] Alon, N.; Moshkovitz, D.; Safra, S., Algorithmic construction of sets for \(k\)-restrictions, ACM Trans. Algorithms, 2, 153-177 (2006) · Zbl 1321.68445
[5] 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, 531-566 (2005) · Zbl 1122.90064
[6] Arkin, E. M.; Mitchell, J. S.B.; Piatko, C. D., Minimum-link watchman tours, Inf. Process. Lett., 86, 203-207 (2003) · Zbl 1173.68757
[7] 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, 513-532 (2009) · Zbl 1191.90087
[8] Berman, P.; Karpinski, M., On some tighter inapproximability results (1999), DIMACS technical report 99-23
[9] Berman, P.; Karpinski, M., Improved approximation lower bounds on small occurrence optimization, Electron. Colloq. Comput. Complex., TR03-008 (2003)
[10] Boissonat, J.; Cérézo, A.; Leblond, J., Shortest paths of bounded curvature in the plane, J. Intell. Robot. Syst., 11, 5-20 (1994) · Zbl 0858.49030
[11] Brimkov, V. E.; Leach, A.; Wu, J.; Mastroianni, M., Approximation algorithms for a geometric set cover problem, Discrete Appl. Math., 160, 1039-1052 (2012) · Zbl 1253.68358
[12] Brodén, B.; Hammar, M.; Nilsson, B. J., Guarding lines and 2-link polygons is APX-hard, (Proceedings of the 13th Canadian Conference on Computational Geometry. Proceedings of the 13th Canadian Conference on Computational Geometry, CCCG’01 (2001)), 45-48
[13] Brönnimann, H.; Goodrich, M. T., Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom., 14, 463-479 (1995) · Zbl 0841.68122
[14] Burnikel, C., Rational points on circles (1998), Max-Planck-Institut für Informatik, technical report MPI-I-98-1-023
[15] Canny, J.; Donald, B.; Ressler, E. K., A rational rotation method for robust geometric algorithms, (Proceedings of the 8th Annual Symposium on Computational Geometry. Proceedings of the 8th Annual Symposium on Computational Geometry, SOCG’92 (1992)), 251-260
[16] Chan, T. M.; Grant, E., Exact algorithms and APX-hardness results for geometric packing and covering problems, Comput. Geom., 47, 112-124 (2014) · Zbl 1283.52032
[17] Chvátal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066
[18] Clarkson, K. L.; Varadarajan, K., Improved approximation algorithms for geometric set cover, Discrete Comput. Geom., 37, 43-58 (2007) · Zbl 1106.68121
[19] Even, G.; Rawitz, D.; Shahar, S., Hitting sets when the VC-dimension is small, Inf. Process. Lett., 95, 358-362 (2005) · Zbl 1184.68632
[20] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 634-652 (1998) · Zbl 1065.68573
[21] Fekete, S. P.; Woeginger, G. J., Angle-restricted tours in the plane, Comput. Geom., 8, 195-218 (1997) · Zbl 1133.90385
[22] Frachard, T., Smooth trajectory planning for a car in a structured world, (Proceedings of the IEEE International Conference on Robotics and Automation (1989)), 318-323
[23] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete problems, (Proceedings of the 6th Annual ACM Symposium on Theory of Computing. Proceedings of the 6th Annual ACM Symposium on Theory of Computing, STOC’74 (1974)), 47-63
[24] Grantson, M.; Levcopoulos, C., Covering a set of points with a minimum number of lines, (Proceedings of the 22nd European Workshop on Computational Geometry (2006)), 145-148
[25] Haussler, D.; Welzl, E., \(ε\)-Nets and simplex range queries, Discrete Comput. Geom., 2, 127-151 (2007) · Zbl 0619.68056
[26] Hochbaum, D. S., Approximation Algorithms for NP-Hard Problems (1997), PWS
[27] Jacobs, P.; Canny, J., Planning smooth paths for mobile robots, (Proceedings of the IEEE International Conference on Robotics and Automation (1989)), 2-7
[28] Jiang, M., On covering points with minimum turns, Int. J. Comput. Geom. Appl., 25, 1-9 (2015) · Zbl 1341.68294
[29] Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci., 9, 256-278 (1974) · Zbl 0296.65036
[30] Kratsch, S.; Philip, G.; Ray, S., Point Line Cover: the easy kernel is essentially tight, (Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’04 (2014)), 1596-1606 · Zbl 1423.68548
[31] Kumar, V. S.A.; Arya, S.; Ramesh, H., Hardness of set cover with intersection 1, (Proceedings of the 27th International Colloquium on Automata, Languages and Programming. Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP’00 (2000)), 624-635 · Zbl 0973.68080
[32] Langerman, S.; Morin, P., Covering things with things, Discrete Comput. Geom., 33, 717-729 (2005) · Zbl 1079.68102
[33] Le Ny, J.; Frazzoli, E.; Feron, E., The curvature-constrained traveling salesman problem for high point densities, (Proceedings of the 46th IEEE Conference on Decision and Control (2007)), 5985-5990
[34] Lovasz, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127
[35] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 960-981 (1994) · Zbl 0814.68064
[36] Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 194-197 (1982) · Zbl 0507.90025
[38] Mustafa, N. H.; Ray, S., Improved results on geometric hitting set problems, Discrete Comput. Geom., 44, 883-895 (2010) · Zbl 1207.68420
[39] Mustafa, N. H.; Raman, R.; Ray, S., QPTAS for geometric set-cover problems via optimal separators (2014)
[40] Pach, J.; Agarwal, P. K., Combinatorial Geometry (1995), John Wiley: John Wiley New York · Zbl 0881.52001
[41] Pach, J.; Tardos, G., Tight lower bounds for the size of epsilon-nets, J. Am. Math. Soc., 26, 645-658 (2013) · Zbl 1268.52011
[42] Raz, R.; Safra, S., A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, (Proceedings of the 29th Annual ACM Symposium on Theory of Computing. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC’97 (1997)), 475-484 · Zbl 0963.68175
[43] Slavík, P., A tight analysis of the greedy algorithm for set cover, J. Algorithms, 25, 237-254 (1997) · Zbl 0887.68040
[44] Stein, C.; Wagner, D. P., Approximation algorithms for the minimum bends traveling salesman problem, (Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization. Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization, IPCO’01 (2001)), 406-421 · Zbl 1010.90519
[45] Wang, J.; Li, W.; Chen, J., A parameterized algorithm for the hyperplane-cover problem, Theor. Comput. Sci., 411, 4005-4009 (2010) · Zbl 1234.68447
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.