High-dimensional shape fitting in linear time (Q1762950)

Let \(P\) be a set of \(n\) points in \(\Re^d\). The radius of a \(k\)-dimensional flat \({\mathcal F}\) with respect to \(P\), which we denote by \({\mathcal RD}({\mathcal F},P)\), is defined to be \(\max_{p \in P} \text{dist}({\mathcal F},p)\), where \(\text{dist}({\mathcal F},p)\) denotes the Euclidean distance between \(p\) and its projection onto \({\mathcal F}\). The \(k\)-flat radius of \(P\), which we denote by \(R^{\text{opt}_k}(P)\), is the minimum, over all \(k\)-dimensional flats \({\mathcal F}\), of \({\mathcal RD}({\mathcal F},P)\). We consider the problem of computing \(R^{\text{opt}_k}(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 < \varepsilon \leq 1\), returns a \(k\)-flat \({\mathcal F}\) such that \({\mathcal RD}({\mathcal F},P) \leq (1 + \varepsilon) R^{\text{opt}_k}(P)\). The algorithm runs in \(O(nd C_{\varepsilon,k})\) time, where \(C_{\varepsilon,k}\) is a constant that depends only on \(\varepsilon\) 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 \(d n^{O(k/\varepsilon^c)}\), where \(c\) is an appropriate constant.