Document Open Access Logo

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Authors Nil Mamano , Alon Efrat, David Eppstein, Daniel Frishberg , Michael T. Goodrich , Stephen Kobourov , Pedro Matias , Valentin Polishchuk

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2019.51.pdf
  • Filesize: 0.66 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational geometry
Keywords
  • Nearest-neighbors
  • Nearest-neighbor chain
  • motorcycle graph
  • straight skeleton
  • multi-fragment algorithm
  • Euclidean TSP
  • Steiner TSP

Metrics

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

Abstract

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.

Cite As Get BibTex

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.51

Author Details

Nil Mamano
  • Department of Computer Science, University of California, Irvine, USA
Alon Efrat
  • Department of Computer Science, University of Arizona, Tucson, USA
David Eppstein
  • Department of Computer Science, University of California, Irvine, USA
Daniel Frishberg
  • Department of Computer Science, University of California, Irvine, USA
Michael T. Goodrich
  • Department of Computer Science, University of California, Irvine, USA
Stephen Kobourov
  • Department of Computer Science, University of Arizona, Tucson, USA
Pedro Matias
  • Department of Computer Science, University of California, Irvine, USA
Valentin Polishchuk
  • Communications and Transport Systems, ITN, Linköping University, Sweden

Funding

  • Eppstein, David: Supported in part by NSF grants CCF-1618301 and CCF-1616248.
  • Goodrich, Michael T.: Supported in part by NSF grant 1815073.
  • Kobourov, Stephen: Supported in part by NSF grants CCF-1740858, CCF-1712119, DMS-1839274, and DMS-1839307.

References

  1. Pankaj K. Agarwal and Jiří Matoušek. Ray Shooting and Parametric Search. SIAM Journal on Computing, 22(4):794-806, 1993. Google Scholar
  2. Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bernd Gärtner. A novel type of skeleton for polygons. In J. UCS The Journal of Universal Computer Science, pages 752-761. Springer, 1996. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753-782, 1998. Google Scholar
  4. Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891-923, 1998. Google Scholar
  5. Jon Jouis Bentley. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 4(4):387-411, 1992. Google Scholar
  6. Jon Louis Bentley. Experiments on Traveling Salesman Heuristics. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '90, pages 91-99, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics. Google Scholar
  7. Sergei N. Bespamyatnikh. An Optimal Algorithm for Closest-Pair Maintenance. Discrete & Computational Geometry, 19(2):175-195, February 1998. Google Scholar
  8. Judith Brecklinghaus and Stefan Hougardy. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, 43(3):259-261, 2015. Google Scholar
  9. Michel Bruynooghe. New methods in automatic classification of numerous taxonomic data. Statistics and data analysis, 2(3):24-42, 1977. Google Scholar
  10. Michel Bruynooghe. Classification ascendante hiérarchique des grands ensembles de données: un algorithme rapide fondé sur la construction des voisinages réductibles. Les cahiers de l’analyse de données, 3:7-33, 1978. Google Scholar
  11. Fernando Cacciola. A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes. 2nd CGAL User Workshop, January 2004. URL: http://www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf.
  12. Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.24.
  13. Siu-Wing Cheng, Liam Mencel, and Antoine Vigneron. A Faster Algorithm for Computing Straight Skeletons. ACM Trans. Algorithms, 12(3):44:1-44:21, April 2016. Google Scholar
  14. Siu-Wing Cheng and Antoine Vigneron. Motorcycle Graphs and Straight Skeletons. Algorithmica, 47(2):159-182, February 2007. Google Scholar
  15. F. Cloppet, J. M. Oliva, and G. Stamon. Angular bisector network, a simplified generalized Voronoi diagram: application to processing complex intersections in biomedical images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(1):120-128, January 2000. Google Scholar
  16. Gérard Cornuéjols, Jean Fonlupt, and Denis Naddef. The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming, 33(1):1-27, September 1985. Google Scholar
  17. Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM J. Discrete Mathematics, 31(2):805-824, 2017. Google Scholar
  18. Zdeněk Dvořák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30(2):1095-1101, 2016. Google Scholar
  19. Mehdi El Krari, Belaïd Ahiod, and Bouazza El Benani. An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem. In Ajith Abraham, Abdelkrim Haqiq, Adel M. Alimi, Ghita Mezzour, Nizar Rokbani, and Azah Kamilah Muda, editors, Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016), pages 278-287, Cham, 2017. Springer International Publishing. Google Scholar
  20. D. Eppstein and J. Erickson. Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete & Computational Geometry, 22(4):569-592, December 1999. Google Scholar
  21. David Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. Journal of Experimental Algorithmics (JEA), 5:1, 2000. Google Scholar
  22. David Eppstein, Michael T. Goodrich, Doruk Korkmaz, and Nil Mamano. Defining equitable geographic districts in road networks via stable matching. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 52. ACM, 2017. Google Scholar
  23. David Eppstein, Michael T. Goodrich, and Nil Mamano. Algorithms for stable matching and clustering in a grid. In International Workshop on Combinatorial Image Analysis, pages 117-131. Springer, 2017. Google Scholar
  24. David Eppstein, Michael T. Goodrich, and Nil Mamano. Reactive Proximity Data Structures for Graphs. In Michael A. Bender, Martín Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics, pages 777-789, Cham, 2018. Springer International Publishing. Google Scholar
  25. David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In 25th ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, September 2017. Google Scholar
  26. Michael T. Goodrich and Roberto Tamassia. Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations. In Proceedings of the Ninth Annual Symposium on Computational Geometry, SCG '93, pages 318-327, New York, NY, USA, 1993. ACM. Google Scholar
  27. Christos H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science, 4:237-244, June 1977. Google Scholar
  28. Monika R. Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55(1):3-23, 1997. Google Scholar
  29. Stefan Huber and Martin Held. A fast straight-skeleton algorithm based on generalized motorcycle graphs. International Journal of Computational Geometry & Applications, 22(05):471-498, 2012. Google Scholar
  30. David S. Johnson and Lyle A. McGeoch. The traveling salesman problem: A case study in local optimization. In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, pages 215-310. John Wiley and Sons, Chichester, United Kingdom, 1997. Google Scholar
  31. Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In 51st IEEE Symp. on Foundations of Computer Science (FOCS), pages 153-162, 2010. Google Scholar
  32. Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains, 2019. URL: http://arxiv.org/abs/1902.06875.
  33. Alfonsas Misevicius and Andrius Blazinskas. Combining 2-OPT, 3-OPT and 4-OPT with K-Swap-Kick perturbations for the traveling salesman problem. 17th International Conference on Information and Software Technologies, 2011. Google Scholar
  34. Pablo Moscato and Michael G. Norman. On the Performance of Heuristics on Finite and Infinite Fractal Instances of the Euclidean Traveling Salesman Problem. INFORMS Journal on Computing, 10(2):121-132, 1998. URL: https://doi.org/10.1287/ijoc.10.2.121.
  35. Daniel Müllner. Modern hierarchical, agglomerative clustering algorithms. arXiv e-prints, September 2011. URL: http://arxiv.org/abs/1109.2378.
  36. Fionn Murtagh. A survey of recent advances in hierarchical clustering algorithms. The Computer Journal, 26(4):354-359, 1983. Google Scholar
  37. Hoon Liong Ong and J. B. Moore. Worst-case analysis of two travelling salesman heuristics. Operations Research Letters, 2(6):273-277, 1984. Google Scholar
  38. Lloyd Shapley and Herbert Scarf. On cores and indivisibility. Journal of mathematical economics, 1(1):23-37, 1974. Google Scholar
  39. Antoine Vigneron and Lie Yan. A Faster Algorithm for Computing Motorcycle Graphs. Discrete Comput. Geom., 52(3):492-514, October 2014. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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