We present a randomized algorithm of expected time complexity O(m 2/3 n 2/3log4/3 m+mlog2 m+nlog2 n) for computing bi-chromatic farthest neighbors between n red points and m blue points in ɛ3. The algorithm can also be used to compute all farthest neighbors or external farthest neighbors of n points in ɛ3 in O(n 4/3log4/3 n) expected time. Using these procedures as building blocks, we can compute a Euclidean maximum spanning tree or a minimum-diameter two-partition of n points in ɛ3 in O(n 4/3log7/3 n) expected time. The previous best bound for these problems was O(n 3/2log1/2 n). Our algorithms can be extended to higher dimensions.
We also propose fast and simple approximation algorithms for these problems. These approximation algorithms produce solutions that approximate the true value with a relative accuracy ɛ and run in time O(nɛ(1−k)/2logn) or O(nɛ(1−k)/2log2 n) in k-dimensional space.