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

Nil Mamano, Alon Efrat, David Eppstein +5

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric…