Math @ Duke

Publications [#235509] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Phillips, JM, An efficient algorithm for 2D Euclidean 2center with outliers,
Lecture notes in computer science, vol. 5193 LNCS
(2008),
pp. 6475, ISSN 03029743 [doi]
(last updated on 2017/12/15)
Abstract: For a set P of n points in ℝ2, the Euclidean 2center problem computes a pair of congruent disks of the minimal radius that cover P. We extend this to the (2,k)center problem where we compute the minimal radius pair of congruent disks to cover n∈∈k points of P. We present a randomized algorithm with O(n k 7 log3 n) expected running time for the (2,k)center problem. We also study the (p,k)center problem in ℝ2 under the ℓ∞metric. We give solutions for p∈=∈4 in O(k O(1) n logn) time and for p = 5 in O(k O(1) n log5 n) time. © 2008 SpringerVerlag Berlin Heidelberg.


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

