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