Document Open Access Logo

TSP in a Simple Polygon

Authors Henk Alkema, Mark de Berg , Morteza Monemizadeh, Leonidas Theocharous

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2022.5.pdf
  • Filesize: 0.92 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Traveling Salesman Problem
  • Subexponential algorithms
  • TSP with obstacles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2^O(√nlog n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.

Cite As Get BibTex

Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous. TSP in a Simple Polygon. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.5

Author Details

Henk Alkema
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Mark de Berg
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Morteza Monemizadeh
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Leonidas Theocharous
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands

Funding

HA, MdB, and LT are supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.

References

  1. Jeff Abrahamson and Ali Shokoufandeh. Euclidean TSP on two polygons. Theor. Comput. Sci., 411(7-9):1104-1114, 2010. URL: https://doi.org/10.1016/j.tcs.2009.12.003.
  2. David L. Applegate, Robert E. Bixby, and Vasek Chvátal. Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753-782, 1998. Google Scholar
  4. Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In Howard J. Karloff, editor, Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pages 33-41. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314632.
  5. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563-1581, 2016. URL: https://doi.org/10.1137/130913328.
  6. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61-63, 1962. URL: https://doi.org/10.1145/321105.321111.
  7. T.-H. Hubert Chan and Anupam Gupta. Approximating TSP on metrics with bounded global growth. SIAM J. Comput., 41(3):587-617, 2012. URL: https://doi.org/10.1137/090749396.
  8. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie Mellon University, 1976. Google Scholar
  9. William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2011. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay. An eth-tight exact algorithm for euclidean TSP. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 450-461, 2018. URL: https://doi.org/10.1109/FOCS.2018.00050.
  12. M. R. Garey, Ronald L. Graham, and David S. Johnson. Some NP-complete geometric problems. In STOC, pages 10-22. ACM, 1976. Google Scholar
  13. Marcus Greiff and Anders Robertsson. Optimisation-based motion planning with obstacles and priorities. IFAC-PapersOnLine, 50(1):11670-11676, 2017. 20th IFAC World Congress. URL: https://doi.org/10.1016/j.ifacol.2017.08.1677.
  14. Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. Journal of Computer and System Sciences, 39(2):126-152, 1989. URL: https://doi.org/10.1016/0022-0000(89)90041-X.
  15. Gregory Gutin and Abraham P. Punnen. The Traveling Salesman Problem and Its Variations. Springer, 2002. Google Scholar
  16. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting, ACM '61, pages 71.201-71.204, New York, NY, USA, 1961. ACM. Google Scholar
  17. R. Z. Hwang, R. C. Chang, and Richard C. T. Lee. The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica, 9(4):398-423, 1993. URL: https://doi.org/10.1007/BF01228511.
  18. Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm, 1992. Google Scholar
  19. Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP. In 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of LIPIcs, pages 55:1-55:15, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.55.
  20. Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Wegrzycki. A gap-eth-tight approximation scheme for euclidean TSP. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 351-362. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00043.
  21. Philip N. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput., 37(6):1926-1952, 2008. URL: https://doi.org/10.1137/060649562.
  22. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for subset TSP on planar graphs. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 1812-1830, 2014. URL: https://doi.org/10.1137/1.9781611973402.131.
  23. Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. CoRR, abs/1707.02190, 2017. URL: http://arxiv.org/abs/1707.02190.
  24. Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 474-484, 2018. URL: https://doi.org/10.1109/FOCS.2018.00052.
  25. Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences, 32(3):265-279, 1986. URL: https://doi.org/10.1016/0022-0000(86)90030-9.
  26. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999. URL: https://doi.org/10.1137/S0097539796309764.
  27. Christos H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci., 4(3):237-244, 1977. Google Scholar
  28. Satish Rao and Warren D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In STOC, pages 540-550. ACM, 1998. Google Scholar
  29. Gerhard Reinelt. The Traveling Salesman, Computational Solutions for TSP Applications, volume 840 of Lecture Notes in Computer Science. Springer, 1994. URL: https://doi.org/10.1007/3-540-48661-5.
  30. John Saalweachter and Zygmunt Pizlo. Non-Euclidean Traveling Salesman Problem, pages 339-358. Springer New York, New York, NY, 2008. URL: https://doi.org/10.1007/978-0-387-77131-1_14.
  31. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications. In FOCS, pages 232-243. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743449.
  32. Godfried Toussaint. Oan optimal algorithm for computing the relative convex hull of a set of points in a polygon. In Proceedings of EURASIP, Signal Processing III: Theories and Applications (Part 2), pages 853-856, 1986. Google Scholar
  33. Luca Trevisan. When hamming meets euclid: The approximability of geometric TSP and steiner tree. SIAM J. Comput., 30(2):475-485, 2000. URL: https://doi.org/10.1137/S0097539799352735.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact