An efficient algorithm for 2D Euclidean 2-center with outliers


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Phillips, JM

Published Date

  • December 24, 2008

Published In

Volume / Issue

  • 5193 LNCS /

Start / End Page

  • 64 - 75

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-540-87744-8-6

Citation Source

  • Scopus