Euclidean minimum spanning trees and bichromatic closest pairs Journal Article


Author(s): Agarwal, Pankaj K; Edelsbrunner, Herbert; Schwarzkopf, Otfried ; Welzl, Emo
Article Title: Euclidean minimum spanning trees and bichromatic closest pairs
Affiliation
Abstract: 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}.
Journal Title: Discrete & Computational Geometry
Volume: 6
Issue 1
ISSN: 0179-5376
Publisher: Springer  
Date Published: 1991-12-01
Start Page: 407
End Page: 422
Sponsor: Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648, National Science Foundation under Grant CCR-8714565.
DOI: 10.1007/BF02574698
Open access: no