| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 414327 | Computational Geometry | 2008 | 9 Pages |
Abstract
Given a set of points P⊂Rd and value ε>0, an ε-core-set S⊂P has the property that the smallest ball containing S has radius within 1+ε of the radius of the smallest ball containing P. This paper shows that any point set has an ε-core-set of size ⌈1/ε⌉, and this bound is tight in the worst case. Some experimental results are also given, comparing this algorithm with a previous one, and with a more powerful, but slower one.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
