High-dimensional shape fitting in linear time (Q1762950): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00454-004-1118-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2093867071 / rank
 
Normal rank

Revision as of 20:47, 19 March 2024

scientific article
Language Label Description Also known as
English
High-dimensional shape fitting in linear time
scientific article

    Statements

    High-dimensional shape fitting in linear time (English)
    0 references
    0 references
    0 references
    11 February 2005
    0 references
    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.
    0 references

    Identifiers