EUCLIDEAN MINIMUM SPANNING-TREES AND BICHROMATIC CLOSEST PAIRS

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in E(d) in time O(T(d)(N, N) log(d) N), where T(d)(n, m) is the time required to compute a bichromatic closest pair among n red and m green points in E(d). If T(d)(N, N) = OMEGA-(N 1 + epsilon), for some fixed epsilon > 0, then the running time improves to O(T(d)(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time O(nm log n log m)2/3 + m log2 n + n log2 m) in E3, which yields an O(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3. In d greater-than-or-equal-to 4 dimensions we obtain expected time O(nm)1-1/([d/2] + 1) + epsilon + m log n + n log m) for the bichromatic closest pair problem and O(N2-2/([d/2] + 1) + epsilon) for the Euclidean minimum spanning tree problem, for any positive epsilon.