Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235565] of Pankaj K. Agarwal

Papers Published

  1. 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. 189-201, ISSN 0925-7721
    (last updated on 2017/12/16)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320