Abstract
We analyze an extremely simple approximation algorithm for computing the minimum enclosing ball (or the 1-center) of a set of points in high dimensions. We prove that this algorithm computes a 3/2-factor approximation in any dimension using minimum space in just one pass over the data points.
| Original language | English (US) |
|---|---|
| Pages | 139-142 |
| Number of pages | 4 |
| State | Published - 2006 |
| Externally published | Yes |
| Event | 18th Annual Canadian Conference on Computational Geometry, CCCG 2006 - Kingston, Canada Duration: Aug 14 2006 → Aug 16 2006 |
Conference
| Conference | 18th Annual Canadian Conference on Computational Geometry, CCCG 2006 |
|---|---|
| Country/Territory | Canada |
| City | Kingston |
| Period | 8/14/06 → 8/16/06 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics