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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s00454-004-1118-2 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
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
Property / DOI
 
Property / DOI: 10.1007/S00454-004-1118-2 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 09:15, 11 December 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