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 (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS
(2008),
pp. 6475, ISSN 03029743 [doi]
(last updated on 2018/10/18)
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

