TY - GEN
T1 - New applications of nearest-neighbor chains
T2 - 30th International Symposium on Algorithms and Computation, ISAAC 2019
AU - Mamano, Nil
AU - Eppstein, David
AU - Goodrich, Michael T.
AU - Matias, Pedro
AU - Efrat, Alon
AU - Frishberg, Daniel
AU - Kobourov, Stephen
AU - Polishchuk, Valentin
N1 - Funding Information:
Funding David Eppstein: Supported in part by NSF grants CCF-1618301 and CCF-1616248. Michael T. Goodrich: Supported in part by NSF grant 1815073. Stephen Kobourov: Supported in part by NSF grants CCF-1740858, CCF-1712119, DMS-1839274, and DMS-1839307.
Funding Information:
David Eppstein: Supported in part by NSF grants CCF-1618301 and CCF-1616248. Michael T. Goodrich: Supported in part by NSF grant 1815073.
Publisher Copyright:
© Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk;
PY - 2019/12
Y1 - 2019/12
N2 - 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√n log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n4/3+ε) time for any ε > 0.
AB - 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√n log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n4/3+ε) time for any ε > 0.
KW - Euclidean TSP
KW - Motorcycle graph
KW - Multi-fragment algorithm
KW - Nearest-neighbor chain
KW - Nearest-neighbors
KW - Steiner TSP
KW - Straight skeleton
UR - http://www.scopus.com/inward/record.url?scp=85076355301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076355301&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2019.51
DO - 10.4230/LIPIcs.ISAAC.2019.51
M3 - Conference contribution
AN - SCOPUS:85076355301
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 30th International Symposium on Algorithms and Computation, ISAAC 2019
A2 - Lu, Pinyan
A2 - Zhang, Guochuan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 8 December 2019 through 11 December 2019
ER -