[{"page":"203 - 210","publist_id":"2044","publication_identifier":{"isbn":[]},"language":[{}],"oa_version":"None","status":"public","extern":"1","article_processing_charge":"No","conference":{"location":"Berkeley, CA, United States","end_date":"1990-06-09","name":"SCG: Symposium on Computational Geometry","start_date":"1990-06-07"},"quality_controlled":"1","type":"conference","scopus_import":"1","publication":"Proceedings of the 6th annual symposium on Computational geometry","day":"01","uri_base":"https://research-explorer.app.ist.ac.at","date_published":"1990-01-01T00:00:00Z","abstract":[{"lang":"eng"}],"dc":{"language":["eng"],"date":["1990"],"identifier":["https://research-explorer.app.ist.ac.at/record/4076"],"rights":["info:eu-repo/semantics/closedAccess"],"creator":["Agarwal, Pankaj","Edelsbrunner, Herbert","Schwarzkopf, Otfried","Welzl, Emo"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1145/98524.98567","info:eu-repo/semantics/altIdentifier/isbn/978-0-89791-362-1"],"description":["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."],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"publisher":["ACM"],"title":[" Euclidean minimum spanning trees and bichromatic closest pairs"],"source":["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"]},"publication_status":"published","month":"01","date_updated":"2022-02-16T15:30:22Z","_id":"4076","author":[{"first_name":"Pankaj","last_name":"Agarwal"},{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Otfried","last_name":"Schwarzkopf"},{"last_name":"Welzl","first_name":"Emo"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"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.","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.","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.","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.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, in:, Proceedings of the 6th Annual Symposium on Computational Geometry, ACM, 1990, pp. 203–210."},"main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/98524.98567"}],"date_created":"2018-12-11T12:06:48Z","creator":{"login":"alisjak","id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},"dini_type":"doc-type:conferenceObject"}]