An Efficient Algorithm for 2D Euclidean 2-Center with Outliers

2008/06/26 by Pankaj K. Agarwal, Agarwal, Pankaj K., Jeff M. Phillips +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Robotics and Sensor-Based Localization #cs.CG

paper · pdf · doi:10.48550/arxiv.0806.4326

19 pages, 6 figures. Longer version of paper in ESA08. Adds section on l_\infty (p,k)-center

arxiv created 2008/09/13 · arxiv updated 2009/12/01

Abstract

For a set P of n points in R², 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 R² under the ℓ_∞-metric. We give solutions for p=4 in O(k^O(1) n log n) time and for p=5 in O(k^O(1) n log⁵ n) time.

Related

• Efficient Planar Two-Center Algorithms
• The 2-Center Problem in Three Dimensions
• On the Planar Two-Center Problem and Circular Hulls
• Generalized Center Problems with Outliers
• Covering and Piercing Disks with Two Centers