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

Math @ Duke





.......................

.......................


Publications [#336326] 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, in Second Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 519 LNCS (January, 1991), pp. 105-116, Springer Verlag, ISBN 9783540475668 [doi]
    (last updated on 2023/06/02)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

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