2026-07-23T21:03:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11547 2024-03-06T10:48:17Z ddc:004 open_access

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs Mamano, Nil Efrat, Alon Eppstein, David Frishberg, Daniel Goodrich, Michael T. Kobourov, Stephen Matias, Pedro Polishchuk, Valentin Nearest-neighbors Nearest-neighbor chain motorcycle graph straight skeleton multi-fragment algorithm Euclidean TSP Steiner TSP 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nil Mamano and Alon Efrat and David Eppstein and Daniel Frishberg and Michael T. Goodrich and Stephen Kobourov and Pedro Matias and Valentin Polishchuk 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.51 urn:nbn:de:0030-drops-115477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode