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

Math @ Duke



Publications [#235558] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Edelsbrunner, H; Schwarzkopf, O; Welzl, E, Euclidean minimum spanning trees and bichromatic closest pairs (1990), pp. 203-210
    (last updated on 2018/11/16)

    We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3, which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3.
ph: 919.660.2800
fax: 919.660.2821

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