TREE-WEIGHTED NEIGHBORS AND GEOMETRIC k SMALLEST SPANNING TREES

Abstract

We compute the k smallest spanning trees of a point set in the planar Euclidean metric in time O(n log n log k + k min (k, n)^1/2 log (k/n)), and in the rectilinear metric in time O(n log n + n log log n log k + k ( min {k, n})^1/2 log (k/n)). In three or four dimensions our time bound is O(n^{4/3 + ∊} + k( min {k, n})^1/2 log (k/n)), and in higher dimensions the bound is O(n^{2−2/(⌈d/2⌉+1)+∊} + kn^1/2 log n). Our technique involves a method of computing nearest neighbors using a modified set of distances formed by subtracting tree path lengths from the Euclidean distance.