An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
| dc.creator | Agarwal, Pankaj K. | |
| dc.creator | Phillips, Jeff M. | |
| dc.date | 2008-06-26 | |
| dc.date | 2008-09-13 | |
| dc.date.accessioned | 2026-07-07T10:02:21Z | |
| dc.date.available | 2026-07-07T10:02:21Z | |
| dc.description | 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. | |
| dc.description | 19 pages, 6 figures. Longer version of paper in ESA08. Adds section on l_\infty (p,k)-center | |
| dc.identifier | https://arxiv.org/abs/0806.4326 | |
| dc.identifier | http://arxiv.org/abs/0806.4326 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168946 | |
| dc.subject | Computational Geometry | |
| dc.title | An Efficient Algorithm for 2D Euclidean 2-Center with Outliers | |
| dc.type | text |