Euclidean minimum spanning trees and bichromatic closest pairs (Q1176318)

The important problem of the efficient computation of Euclidean minimum spanning trees on \(N\) points in a fixed dimension space \(E^ d\) is considered. The authors develop \(O(T_ d(N,N)\log^ d N)\) algorithm, \(T_ d(n,m)\) is the time needed for the computation of bichromatic closest pair of \(n\) blue and \(m\) red points in \(E^ d\). Furthermore for \(d=3\) a fast randomized \(O(N^{4/3}\log^{4/3} N)\) algorithm is described. In my opinion the results, the analysis and the randomization technique are new and turn to be an essential tool for researches in computational geometry.