Euclidean minimum spanning trees and bichromatic closest pairs

article Euclidean minimum spanning trees and bichromatic closest pairs published yes Pankaj Agarwal author Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 Otfried Schwarzkopf author Emo Welzl author 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}>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}. Springer1991 eng Discrete & Computational Geometry 0179-5376 1432-044410.1007/BF02574698 61407 - 422 yes P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete & Computational Geometry 6 (1991) 407–422. Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1991. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. 6(1), 407–422. Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Discrete & Computational Geometry, vol. 6, no. 1, Springer, 1991, pp. 407–22, doi:<a href="https://doi.org/10.1007/BF02574698">10.1007/BF02574698</a>. Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Discrete & Computational Geometry. Springer, 1991. <a href="https://doi.org/10.1007/BF02574698">https://doi.org/10.1007/BF02574698</a>. Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. 1991;6(1):407-422. doi:<a href="https://doi.org/10.1007/BF02574698">10.1007/BF02574698</a> P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum spanning trees and bichromatic closest pairs,” Discrete & Computational Geometry, vol. 6, no. 1. Springer, pp. 407–422, 1991. Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1991). Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. Springer. <a href="https://doi.org/10.1007/BF02574698">https://doi.org/10.1007/BF02574698</a> 40612018-12-11T12:06:42Z2022-02-24T15:06:41Z