Math @ Duke

Publications [#235565] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Matoušek, J; Suri, S, Farthest neighbors, maximum spanning trees and related problems in higher dimensions,
Computational Geometry, vol. 1 no. 4
(1992),
pp. 189201, ISSN 09257721
(last updated on 2018/10/22)
Abstract: We present a randomized algorithm of expected time complexity O(m 2 3n 2 3log 4 3m + m log2m + n log2n) for computing bichromatic 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 minimumdiameter twopartition 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ε (1k) 2log n) or O(nε (1k) 2log2n) in kdimensional space. © 1992.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

