Euclidean minimum spanning trees and bichromatic closest pairs
Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Cheong Schwarzkopf, Emo Welzl · 1990
We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time 𝒪(Τd(N, N) logd N), where Τd(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If Τd(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to 𝒪(Τd(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time 𝒪((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an 𝒪(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.