Fast hierarchical clustering and other applications of dynamic closest pairs

摘要: We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based a technique previously used by author Euclidean pairs, we show how to insert and delete objects an n-object set, maintaining pair, in O(n log2 n) time per update O(n) space. With quadratic space, can instead use quadtree-like achieve optimal bound, update. apply these hierarchical clustering, greedy matching, TSP heuristics, discuss other potential applications machine learning, Grobner bases, local improvement algorithms partition placement problems. Experiments our new methods be faster practice than heuristics.