{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:26Z","timestamp":1787337506275,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of O(log n) in polynomial time. We also consider the problem of simultaneously approximating both the angle and the length measure for a TSP tour. In studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. Finally, we consider the extremal value of the angle measure and obtain essentially tight bounds for it. In this paper we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.<\/jats:p>","DOI":"10.1137\/s0097539796312721","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"697-711","source":"Crossref","is-referenced-by-count":44,"title":["The Angular-Metric Traveling Salesman Problem"],"prefix":"10.1137","volume":"29","author":[{"given":"Alok","family":"Aggarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Don","family":"Coppersmith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Motwani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal, P. Raghavan, and H. Tamaki,\n                      Motion planning for a steering\u2010constrained robot through moderate obstacles\n                      , in Proceedings of the Twenty\u2010Seventh Annual ACM Symposium on the Theory of Computing, ACM, New York, 1995, pp. 343\u2013352.","DOI":"10.1145\/225058.225158"},{"key":"R2","first-page":"77","volume":"3","author":"Barraquand and J\u2010C. Latombe J.","year":"1989","journal-title":"Revue d\u2019Intelligence Artificelle"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891837"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Jean\u2010Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jean\u2010Marc Robert, Mariette Yvinec, Convex tours of bounded curvature, Lecture Notes in Comput. Sci., Vol. 855, Springer, Berlin, 1994, 254\u201326596c:68196","DOI":"10.1007\/BFb0049413"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01258291"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0214011"},{"key":"R7","unstructured":"N. Christofides,\n                      Worst\u2010Case Analysis for a New Heuristic for the Traveling Salesman Problem\n                      , Report 388, Graduate School of Industrial Administration, Carnegie\u2013Mellon University, Pittsburgh, PA, 1976."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/oca.4660110104"},{"key":"R9","first-page":"35","volume":"12","author":"Erd\u00f6s Paul","year":"1983","journal-title":"Math. Chronicle"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"T. Fraichard,\n                      Smooth trajectory planning for a car in a structured world\n                      , in Proceedings of the IEEE International Conference on Robotics, IEEE Press, Piscataway, NJ, 1991, pp. 318\u2013323.","DOI":"10.1109\/ROBOT.1991.131595"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R12","unstructured":"L. Guibas,\n                      private communication\n                      , Stanford Univeristy, Palo Alto, CA, 1995."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"P. Jacobs and J. Canny,\n                      Planning smooth paths for mobile robots\n                      , in Proceedings of the IEEE International Conference on Robotics, IEEE Press, Piscataway, NJ, 1989, pp. 2\u20137.","DOI":"10.1109\/ROBOT.1989.99959"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910020"},{"key":"R15","unstructured":"J\u2010P. Laumond,\n                      Finding collision\u2010free smooth trajectories for a non\u2010holonomic mobile robot\n                      , in Proceedings of the IEEE International Conference on Robotics, IEEE Press, Piscataway, NJ, 1987, pp. 1120\u20131123."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,\n                      The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization\n                      , John Wiley, New York, 1985.","DOI":"10.2307\/2582681"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796312721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:25Z","timestamp":1787336065000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796312721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539796312721"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796312721","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}