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

Published

Journal Article

We present a randomized algorithm of expected time complexity O(m 2 3n 2 3log 4 3m + m log2m + n log2n) for computing bi-chromatic farthest neighbors between n red points and m blue points in E3. The algorithm can also be used to compute all farthest neighbors or external farthest neighbors of n points in E3 in O(n 4 3log 4 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 E3 in O(n 4 3log 7 3n) expected time. The previous best bound for these problems was O(n 3 2log 1 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) 2log n) or O(nε (1-k) 2log2n) in k-dimensional space. © 1992.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; MatouĊĦek, J; Suri, S

Published Date

  • January 1, 1992

Published In

Volume / Issue

  • 1 / 4

Start / End Page

  • 189 - 201

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/0925-7721(92)90001-9

Citation Source

  • Scopus