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


Conference Paper

© Springer-Verlag Berlin Heidelberg 1991. We present a randomized algorithm of expected time complexity O(m2/3n2/3log4/3m+mlog2m+nlog2n) 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 ɛ3 in O(n4/3log4/3n) 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 ɛ3 in O(n4/3log7/3n) expected time. The previous best bound for these problems was O(n3/2log1/2n). 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ɛ(1−k)/2logn) or O(nɛ(1−k)/2log2n) in k-dimensional space.

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