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

Math @ Duke



Publications [#235554] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Avraham, RB; Sharir, M, The 2-center problem in three dimensions, Computational Geometry (2012), ISSN 0925-7721 [doi]
    (last updated on 2017/12/16)

    Let P be a set of n points in R 3. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present a randomized algorithm for computing a 2-center of P that runs in O (β (r *) n 2 log 4 n log log n) expected time; here β (r) = 1 / (1 - r / r 0) 3, r * is the radius of the 2-center balls of P, and r 0 is the radius of the smallest enclosing ball of P. The algorithm is near quadratic as long as r * is not too close to r 0, which is equivalent to the condition that the centers of the two covering balls be not too close to each other. This improves an earlier slightly super-cubic algorithm of Agarwal, Efrat, and Sharir (2000) [2] (at the cost of making the algorithm performance depend on the center separation of the covering balls). © 2012 Elsevier B.V. All rights reserved.
ph: 919.660.2800
fax: 919.660.2821

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