In this talk, we will see new applications of the nearest-neighbor chain technique, which originated in the domain of hierarchical clustering. We apply it to a diverse class of geometric problems, such as constructing a TSP tour with the multi-fragment heuristic or constructing motorcycle graphs. We improve the best known runtimes for these problems, and we show new optimal algorithms for other problems, such as the Euclidean greedy matching problem and the closest pair problem. To achieve these results, we show how the nearest-neighbor chain algorithm can be implemented using approximate nearest-neighbor queries instead of the usual, but more expensive, exact nearest-neighbor queries.
Joint work with David Eppstein, Daniel Frishberg, Michael Goodrich, and Pedro Matias