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

Math @ Duke



Publications [#235384] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Edelsbrunner, H; Schwarzkopf, O; Welzl, E, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, vol. 6 no. 1 (1991), pp. 407-422, ISSN 0179-5376 [doi]
    (last updated on 2017/12/12)

    We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in E d in time O(F d (N,N) log d N), where F d (n,m) is the time required to compute a bichromatic closest pair among n red and m green points in E d . If F d (N,N)=Ω(N 1+ε), for some fixed e{open}>0, then the running time improves to O(F d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time O((nm log n log m)2/3+m log2 n+n log2 m) in E 3, which yields an O(N 4/3 log4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree of N points in E 3. In d≥4 dimensions we obtain expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest pair problem and O(N 2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive e{open}. © 1991 Springer-Verlag New York Inc.
ph: 919.660.2800
fax: 919.660.2821

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