{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T18:57:42Z","timestamp":1757703462081,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T00:00:00Z","timestamp":1717545600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T00:00:00Z","timestamp":1717545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE407\/21-1"],"award-info":[{"award-number":["FE407\/21-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004871","name":"Technische Universit\u00e4t Braunschweig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004871","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate several geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity, approximation results, and open problems dating back to work by Arkin et al.\u00a0in 2001. Many new practical applications have spawned variants: For <jats:italic>full coverage<\/jats:italic>, all points have to be covered, for <jats:italic>subset coverage<\/jats:italic>, specific points have to be covered, and for <jats:italic>penalty coverage<\/jats:italic>, points may be left uncovered by incurring a penalty. We show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open <jats:italic>Problem\u00a053<\/jats:italic> in <jats:italic>The Open Problems Project<\/jats:italic> edited by Demaine, Mitchell and O\u2019Rourke. We also prove NP-hardness of finding a <jats:italic>subset<\/jats:italic> cycle cover of minimum turn cost in <jats:italic>thin<\/jats:italic> grid graphs, for which Arkin et al.\u00a0gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. We also provide a number of positive results. In particular, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for grid-based instances, based on LP\/IP techniques. These geometric versions allow many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants); our approximation factors improve the combinatorial ones of Arkin et al.<\/jats:p>","DOI":"10.1007\/s00224-024-10178-8","type":"journal-article","created":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T08:02:15Z","timestamp":1717574535000},"page":"1207-1238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["What Goes Around Comes Around: Covering Tours and Cycle Covers with Turn Costs"],"prefix":"10.1007","volume":"68","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Krupke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,5]]},"reference":[{"issue":"6","key":"10178_CR1","doi-asserted-by":"publisher","first-page":"1814","DOI":"10.1137\/S0097539700374550","volume":"31","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Biedl, T.C., Lazard, S., Robbins, S., Suri, S., Whitesides, S.: Curvature-constrained shortest paths in a convex polygon. SIAM J. Comp. 31(6), 1814\u20131851 (2002)","journal-title":"SIAM J. Comp."},{"issue":"6","key":"10178_CR2","doi-asserted-by":"publisher","first-page":"1739","DOI":"10.1137\/S0097539796307790","volume":"30","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Wang, H.: Approximation algorithms for curvature-constrained shortest paths. SIAM J. Comp. 30(6), 1739\u20131772 (2000)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"10178_CR3","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539796312721","volume":"29","author":"A Aggarwal","year":"1999","unstructured":"Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., Schieber, B.: The angular-metric traveling salesman problem. SIAM J. Comp. 29(3), 697\u2013711 (1999)","journal-title":"SIAM J. Comp."},{"issue":"4","key":"10178_CR4","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1080\/02331934.2016.1276905","volume":"66","author":"O Aichholzer","year":"2017","unstructured":"Aichholzer, O., Fischer, A., Fischer, F., Meier, J.F., Pferschy, U., Pilz, A., Stan\u011bk, R.: Minimization and maximization versions of the quadratic travelling salesman problem. Optimization 66(4), 521\u2013546 (2017)","journal-title":"Optimization"},{"key":"10178_CR5","unstructured":"Arkin, E.M., Bender, M.A., Demaine, E.D., Fekete, S.P., Mitchell, J.S.B., Sethia, S: Optimal covering tours with turn costs. In: Proceedings of the 12th ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 138\u2013147 (2001)"},{"issue":"3","key":"10178_CR6","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/S0097539703434267","volume":"35","author":"EM Arkin","year":"2005","unstructured":"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. Comp. 35(3), 531\u2013566 (2005)","journal-title":"SIAM J. Comp."},{"issue":"1\u20132","key":"10178_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0925-7721(00)00015-8","volume":"17","author":"EM Arkin","year":"2000","unstructured":"Arkin, E.M., Fekete, S.P., Mitchell, J.S.B.: Approximation algorithms for lawn mowing and milling. Comp. Geom. 17(1\u20132), 25\u201350 (2000)","journal-title":"Comp. Geom."},{"key":"10178_CR8","doi-asserted-by":"crossref","unstructured":"Astroza, S., Patil, P.N., Smith, K.I., Bhat, C.R.: Transportation planning to accommodate needs of wind energy projects. In: Transportation research board\u2013annual meeting, pp. 10\u201318 (2017). Article 17-05309","DOI":"10.3141\/2669-02"},{"key":"10178_CR9","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"G Ausiello","year":"2007","unstructured":"Ausiello, G., Bonifaci, V., Leonardi, S., Marchetti-Spaccamela, A.: Prize-collecting traveling salesman and related problems. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC (2007)"},{"key":"10178_CR10","unstructured":"Becker, A.T., Debboun, M., Fekete, S.P., Krupke, D., Nguyen, A.: Zapping Zika with a mosquito-managing drone: computing optimal flight patterns with minimum turn cost. In: Proc. 33rd Symp. Comp. Geom. (SoCG), pp. 62:1\u201362:5 (2017). Video at https:\/\/www.youtube.com\/watch?v=SFyOMDgdNao"},{"key":"10178_CR11","unstructured":"Benbernou, N.M.: Geometric Algorithms for Reconfigurable Structures. Ph.D. thesis, Massachusetts Institute of Technology (2011)"},{"key":"10178_CR12","unstructured":"Biniaz, A.: Acute tours in the plane. In: Symposium on Computational Geometry (SoCG), pp. 16:1\u201316:8 (2022)"},{"key":"10178_CR13","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., Lazard, S.: A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles. In: Proc. 12th Symp. Comp. Geom. (SoCG), pp. 242\u2013251 (1996)","DOI":"10.1145\/237218.237393"},{"key":"10178_CR14","doi-asserted-by":"crossref","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience (1997)","DOI":"10.1002\/9781118033142"},{"key":"10178_CR15","doi-asserted-by":"crossref","unstructured":"de\u00a0Assis, I.R., de\u00a0Souza, C.C.: Experimental evaluation of algorithms for the orthogonal milling problem with turn costs. In: Proc. 10th Symp. Exp. Alg. (SEA), pp. 304\u2013314 (2011)","DOI":"10.1007\/978-3-642-20662-7_26"},{"key":"10178_CR16","unstructured":"Demaine, E.D., Mitchell, J.S.B., Joseph, O.: The Open Problems Project. http:\/\/cs.smith.edu\/~orourke\/TOPP\/"},{"issue":"3","key":"10178_CR17","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/2372560","volume":"79","author":"LE Dubins","year":"1957","unstructured":"Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American J. Math. 79(3), 497\u2013516 (1957)","journal-title":"American J. Math."},{"key":"10178_CR18","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Krupke, D.: Covering tours and cycle covers with turn costs: Hardness and approximation. In: International Conference on Algorithms and Complexity (CIAC), pp. 224\u2013236 (2019)","DOI":"10.1007\/978-3-030-17402-6_19"},{"key":"10178_CR19","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Krupke, D.: Practical methods for computing large covering tours and cycle covers with turn cost. In: Proc. 21st SIAM Workshop Alg. Engin. Exp. (ALENEX) (2019)","DOI":"10.1137\/1.9781611975499.15"},{"key":"10178_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0925-7721(96)00012-0","volume":"8","author":"SP Fekete","year":"1997","unstructured":"Fekete, S.P., Woeginger, G.J.: Angle-restricted tours in the plane. Comp. Geom. 8, 195\u2013218 (1997)","journal-title":"Comp. Geom."},{"key":"10178_CR21","doi-asserted-by":"crossref","unstructured":"Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F.A., Whitesides, S., Yu, N.: Milling a graph with turn costs: a parameterized complexity perspective. In: Proc 36th Worksh. Graph Theo. Conc. Comp. Sci. (WG), pp. 123\u2013134 (2010)","DOI":"10.1007\/978-3-642-16926-7_13"},{"issue":"2","key":"10178_CR22","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comp. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comp."},{"key":"10178_CR23","unstructured":"Krupke, D.: Algorithm Engineering for Hard Problems in Computational Geometry. PhD thesis, Braunschweig University of Technology, Germany (2022)"},{"key":"10178_CR24","doi-asserted-by":"crossref","unstructured":"Krupke, D.: Near-optimal coverage path planning with turn costs. In: Proc. 26st SIAM Workshop Alg. Engin. Exp. (ALENEX), pp. 118\u2013132 (2024)","DOI":"10.1137\/1.9781611977929.9"},{"key":"10178_CR25","unstructured":"Lazard, S., Reif, J., Wang, H.: The complexity of the two dimensional curvature-constrained shortest-path problem. In: Proc. 3rd Worksh. Alg. Found. Robotics (WAFR), pp. 49\u201357 (1998)"},{"key":"10178_CR26","unstructured":"Olaf, M.: Winkelminimierung bei \u00dcberdeckungsproblemen in Graphen. Diplomarbeit, Technische Universit\u00e4t Berlin (2009)"},{"key":"10178_CR27","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th ACM Symp. Theo. Comput. (STOC), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"10178_CR28","doi-asserted-by":"crossref","unstructured":"Stein, C., Wagner, D.P.: Approximation algorithms for the minimum bends traveling salesman problem. In: Proc. 8th Int. Conf. Int. Prog. Comb. Opt. (IPCO), pp. 406\u2013422 (2001)","DOI":"10.1007\/3-540-45535-3_32"},{"key":"10178_CR29","doi-asserted-by":"crossref","unstructured":"Takei, R., Tsai, R., Shen, H., Landa, Y.: A practical path-planning algorithm for a simple car: A Hamilton-Jacobi approach. In: Proc. 29th American Cont. Conf. (ACC), pp. 6175\u20136180 (2010)","DOI":"10.1109\/ACC.2010.5531607"},{"issue":"4","key":"10178_CR30","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1020853410145","volume":"6","author":"S Winter","year":"2002","unstructured":"Winter, S.: Modeling costs of turns in route planning. GeoInformatica 6(4), 345\u2013361 (2002)","journal-title":"GeoInformatica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10178-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10178-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10178-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:53:38Z","timestamp":1729850018000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10178-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,5]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10178"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10178-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,6,5]]},"assertion":[{"value":"24 April 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}