Euclidean minimum spanning trees and bichromatic closest pairs Agarwal, Pankaj Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Schwarzkopf, Otfried Welzl, Emo We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in Ed in time O(Fd (N,N) logd N), where Fd (n,m) is the time required to compute a bichromatic closest pair among n red and m green points in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}&gt;0, then the running time improves to O(Fd (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≥4 dimensions we obtain expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive e{open}. Springer 1991 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4061 Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):407-422. doi:<a href="https://doi.org/10.1007/BF02574698">10.1007/BF02574698</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/BF02574698 info:eu-repo/semantics/altIdentifier/issn/0179-5376 info:eu-repo/semantics/altIdentifier/e-issn/1432-0444 info:eu-repo/semantics/openAccess