High-dimensional shape fitting in linear time
type: Item
instance of: scholarly article
title: High-dimensional shape fitting in linear time
zbMATH Open document ID: 1101.68909
author: Sariel Har-Peled
author: Kasturi Varadarajan
published in: Discrete \& Computational Geometry
publication date: 2005-02-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 2133697
MaRDI profile type: Publication
full work available at URL: s00454-004-1118-2
OpenAlex ID: W2093867071
DOI: 10.1007/S00454-004-1118-2
Recommended article: High-dimensional shape fitting in linear time
Recommended article: Shape Fitting on Point Sets with Probability Distributions
Recommended article: Q6104071
Recommended article: Q2957523
Recommended article: Q3435602
Recommended article: Q4247400
Recommended article: Q4447312
Recommended article: Matching the LBO eigenspace of non-rigid shapes via high order statistics
Recommended article: Q4808947
description: scientific article; zbMATH DE number 2133697