Euclidean minimum spanning trees and bichromatic closest pairs

P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, ACM, 1990, pp. 203–210.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ;
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(Td(N, N) logd N), where Td(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets 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/3log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3.
Publishing Year
Date Published
1990-01-01
Page
203 - 210
Conference
SCG: Symposium on Computational Geometry
IST-REx-ID

Cite this

Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. In: ACM; 1990:203-210. doi:10.1145/98524.98567
Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1990). Euclidean minimum spanning trees and bichromatic closest pairs (pp. 203–210). Presented at the SCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/98524.98567
Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs,” 203–10. ACM, 1990. https://doi.org/10.1145/98524.98567.
P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “ Euclidean minimum spanning trees and bichromatic closest pairs,” presented at the SCG: Symposium on Computational Geometry, 1990, pp. 203–210.
Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1990. Euclidean minimum spanning trees and bichromatic closest pairs. SCG: Symposium on Computational Geometry 203–210.
Agarwal, Pankaj, et al. Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs. ACM, 1990, pp. 203–10, doi:10.1145/98524.98567.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar