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

Journal Article

For a set P of n points in ℝ , 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 log n) expected running time for the (2,k)-center problem. We also study the (p,k)-center problem in ℝ under the ℓ -metric. We give solutions for p∈=∈4 in O(k n logn) time and for p = 5 in O(k n log n) time. © 2008 Springer-Verlag Berlin Heidelberg. 2 7 3 2 O(1) O(1) 5 ∞

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Phillips, JM

Published Date

  • January 1, 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