Faster algorithms for some geometric graph problems in higher dimensions
Paul B. Callahan, S. Rao Kosaraju · 1993
We show how to apply the well-separated pair decomposition of a point-set P in ! d to significantly improve known time bounds on several geometric graph problems. We first present an algorithm to find an approximate Euclidean minimum spanning tree of P whose weight is at most 1 + ffl times the exact minimum. We achieve a time complexity of O(n log n + (ffl \\Gammad=2 log 1 ffl )n), improving the best known bound of O(ffl \\Gammad n log n). We then show how to construct a graph with O(ffl \\Gammad+1 n) edges in which the shortest path between any pair of points is within 1 + ffl of the Euclidean distance. Our time complexity is O(n log n+(ffl \\Gammad log 1 ffl )n), a significant improvement over the best previous algorithm that produces a graph of this size. Finally, we show how to compute the exact Euclidean minimum spanning tree in time O(T d (n; n) log n), where T d (m; n) is the time to find the bichromatic closest pair between m red points and n blue points. The previo...