Let P be a set of n points in Rd.
The radius of a k-dimensional flat F with respect to
P, which we denote by rad(F,P), is defined to be
maxp in P D(F,p), where
D(F,p) denotes the Euclidean distance between p
and its projection onto F. The k-flat radius of
P, which we denote by krad(P), is the minimum, over
all k-dimensional flats F, of
rad(F,P). We consider the problem of computing
krad(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 NP-hard even for k =
1. We present an algorithm that, given P and a parameter
0 < µ <= 1, returns a k-flat F such that
rad(F,P) <=(1 + µ) krad(P). The algorithm runs
in O(nd Cµ,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
O(d nk/µ^5).