# Farthest neighbors, maximum spanning trees and related problems in higher dimensions

Conference Paper

We present a randomized algorithm of expected time complexity O(m n2/3log m+mlog m+nlog n) for computing bi-chromatic farthest neighbors between nred points and m blue points in ɛ3. The algorithm can also be used to compute all farthest neighbors or external farthest neighbors of n points in ɛ in O(n log n) expected time. Using these procedures as building blocks, we can compute a Euclidean maximum spanning tree or a minimum-diameter two-partition of n points in ɛ in O(n log n) expected time. The previous best bound for these problems was O(n log n). Our algorithms can be extended to higher dimensions. We also propose fast and simple approximation algorithms for these problems. These approximation algorithms produce solutions that approximate the true value with a relative accuracy ɛ and run in time O(nɛ logn) or O(nɛ log n) in k-dimensional space. 2/3 4/3 2 2 3 4/3 4/3 3 4/3 7/3 3/2 1/2 (1−k)/2 (1−k)/2 2

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Matoušek, J; Suri, S

### Published Date

- January 1, 1991

### Published In

### Volume / Issue

- 519 LNCS /

### Start / End Page

- 105 - 116

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 13 (ISBN-13)

- 9783540475668

### Digital Object Identifier (DOI)

- 10.1007/BFb0028254

### Citation Source

- Scopus