Farthest neighbors, maximum spanning trees and related problems in higher dimensions
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.
Agarwal, PK; Matoušek, J; Suri, S
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)