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

Math @ Duke



Publications [#235509] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Phillips, JM, An efficient algorithm for 2D Euclidean 2-center with outliers, Lecture notes in computer science, vol. 5193 LNCS (2008), pp. 64-75, ISSN 0302-9743 [doi]
    (last updated on 2018/03/22)

    For a set P of n points in ℝ2, the Euclidean 2-center 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 Springer-Verlag Berlin Heidelberg.
ph: 919.660.2800
fax: 919.660.2821

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