An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(12)- Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
- On the planar two-center problem and circular hulls
- On the complexity of some problems of searching for a family of disjoint clusters
- A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks
- An \(O(n\log n)\)-time algorithm for the \(k\)-center problem in trees
- The 2-center problem in three dimensions
- Data reduction for weighted and outlier-resistant clustering
- An O(n n)-time algorithm for the k-center problem in trees
- A streaming algorithm for 2-center with outliers in high dimensions
- Optimal algorithm for the planar two-center problem
- Optimal algorithm for the planar two-center problem
- Approximation algorithm for the kinetic robust \(k\)-center problem
This page was built for publication: An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541075)
