# Euclidean minimum spanning trees and bichromatic closest pairs

Journal Article

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in E in time O(T (N, N) log N), where T (n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in E . If T (N, N) = Ω(N ), for some fixed ε > 0, then the running time improves to O(T (N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets pair in expected time O((nm log n log m) +m log n + n log m) in E , which yields an O(N log N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E . d d d 1+ε 2 2 3 4/3 4/3 3 d d d d 2/3

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Edelsbrunner, H; Schwarzkopf, O; Welzl, E

### Published Date

- January 1, 1990

### Start / End Page

- 203 - 210

### Digital Object Identifier (DOI)

- 10.1145/98524.98567

### Citation Source

- Scopus