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

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

2008-06-26

arxiv.org/abs/0806.4326v2

Computer Science

Computational Geometry

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

Scientific paper

For a set P of n points in R^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 log^3 n) expected running time for the (2,k)-center problem. We also study the (p,k)-center problem in R}^2 under the \ell_\infty-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^5 n) time.

Affiliated with

Also associated with

No associations

Rating

An Efficient Algorithm for 2D Euclidean 2-Center with Outliers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient Algorithm for 2D Euclidean 2-Center with Outliers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Algorithm for 2D Euclidean 2-Center with Outliers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-246554