## Abstract

Let P be a set of n points in ℝ^{d}, and for any integer 0 ≤ κ ≤ d - 1, let RD_{κ}(P) denote the minimum over all κ-flats ℱ of max_{pεP} dist(p, ℱ). We present an algorithm that computes, for any 0 < ε < 1, a κ-flat that is within a distance of (1 + ε)RD_{κ}(P) from each point of P. The running time of the algorithm is dn^{O(κ/ε5log(1/ε))}. The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P. The size of this "core-set" depends on κ and ε but is independent of the dimension. This approach also extends to the case where we want to find a κ-flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension κ, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when κ > 1 or j > 1.

Original language | English (US) |
---|---|

Pages | 312-318 |

Number of pages | 7 |

DOIs | |

State | Published - 2002 |

Event | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain Duration: Jun 5 2002 → Jun 7 2002 |

### Other

Other | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 6/5/02 → 6/7/02 |

## Keywords

- Computational convexity
- Projective clustering

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics