Math @ Duke

Publications [#235554] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Avraham, RB; Sharir, M, The 2center problem in three dimensions,
Computational Geometry
(2012), ISSN 09257721 [doi]
(last updated on 2018/10/18)
Abstract: Let P be a set of n points in R 3. The 2center problem for P is to find two congruent balls of minimum radius whose union covers P. We present a randomized algorithm for computing a 2center 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 2center 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 supercubic 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

