## Abstract

Let P be a set of n points in ℝ^{d}. The radius of a k-dimensional flat F with respect to P, denoted by RD(F, P), is defined to be max_{p∈P} dist(F, p), where dist(F, p) denotes the Euclidean distance between p and its projection onto F. The k-flat radius of P, which we denote by R_{k}^{opt}(P), is the minimum, over all k-dimensional flats F, of RD(F, P). We consider the problem of computing R_{k}^{opt}(P) for a given set of points P. We are interested in the high-dimensional case where d is a part of the input and not a constant. This problem is ℕℙ-hard even for k = 1. We present an algorithm that, given P and a parameter 0 < ε ≤ 1, returns a k-flat F such that RD(F, P) ≤ (1 + ε)R_{k}^{opt}(P). The algorithm runs in O(ndC_{ε,k}) time, where C_{ε,k} is a constant that depends only on ε and k. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of dn^{O(k/εc)} where c is an appropriate constant.

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

Pages | 39-47 |

Number of pages | 9 |

DOIs | |

State | Published - 2003 |

Event | Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003 |

### Other

Other | Nineteenth Annual Symposium on Computational Geometry |
---|---|

Country/Territory | United States |

City | san Diego, CA |

Period | 6/8/03 → 6/10/03 |

## Keywords

- Computational convexity
- Projective clustering

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics