Donald Bren School of Information and Computer Sciences

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 metrics in time O(n log n + n log log n log k + kmin(k,n)^1/2 log(k/n)). In three or four dimensions our time bound is O(n^4/3+c + k min(k, n)^1/2 log(k/n)), and in higher dimensions the bound is O(n^2-2([d/2]+1)+c + kn^1/2 log n).