--- _id: '4076' abstract: - lang: eng text: 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. article_processing_charge: No author: - first_name: Pankaj full_name: Agarwal, Pankaj last_name: Agarwal - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Otfried full_name: Schwarzkopf, Otfried last_name: Schwarzkopf - first_name: Emo full_name: Welzl, Emo last_name: Welzl citation: ama: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. In: Proceedings of the 6th Annual Symposium on Computational Geometry. ACM; 1990:203-210. doi:10.1145/98524.98567' apa: 'Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1990). Euclidean minimum spanning trees and bichromatic closest pairs. In Proceedings of the 6th annual symposium on Computational geometry (pp. 203–210). Berkeley, CA, United States: ACM. https://doi.org/10.1145/98524.98567' chicago: Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” In Proceedings of the 6th Annual Symposium on Computational Geometry, 203–10. ACM, 1990. https://doi.org/10.1145/98524.98567. ieee: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “ Euclidean minimum spanning trees and bichromatic closest pairs,” in Proceedings of the 6th annual symposium on Computational geometry, Berkeley, CA, United States, 1990, pp. 203–210. ista: 'Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1990. Euclidean minimum spanning trees and bichromatic closest pairs. Proceedings of the 6th annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 203–210.' mla: Agarwal, Pankaj, et al. “ Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–10, doi:10.1145/98524.98567. short: P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210. conference: end_date: 1990-06-09 location: Berkeley, CA, United States name: 'SCG: Symposium on Computational Geometry' start_date: 1990-06-07 date_created: 2018-12-11T12:06:48Z date_published: 1990-01-01T00:00:00Z date_updated: 2022-02-16T15:30:22Z day: '01' doi: 10.1145/98524.98567 extern: '1' language: - iso: eng main_file_link: - url: https://dl.acm.org/doi/10.1145/98524.98567 month: '01' oa_version: None page: 203 - 210 publication: Proceedings of the 6th annual symposium on Computational geometry publication_identifier: isbn: - 978-0-89791-362-1 publication_status: published publisher: ACM publist_id: '2044' quality_controlled: '1' scopus_import: '1' status: public title: ' Euclidean minimum spanning trees and bichromatic closest pairs' type: conference user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 year: '1990' ...