The nearest-neighbor chain algorithm was designed in the 70's to speed up agglomerative hierarchical clustering methods. That line of work seemed to end there, but our recent insight was that this algorithm can be applied to other problems. In this talk, we introduce the algorithmic ideas behind it, and how they apply to a variety of problems, such as stable matching in restricted settings, Euclidean TSP, computing straight skeletons, and shortest superstring. For instance, with this approach we reduce the runtime for the multi-fragment heuristic for Euclidean TSP from O(n^2) to O(n log n). For some problems, the work is still ongoing, but nearest-neighbor chains provide an interesting new approach.
Joint work with Alon Efrat, David Eppstein, Daniel Frishberg, Michael Goodrich, Stephen Kouborov, Pedro Matias, and Valentin Polishchuk