High-Dimensional Shape Fitting in Linear Time |
| |
Authors: | Email author" target="_blank">Sariel?Har-PeledEmail author Email author" target="_blank">Kasturi R?VaradarajanEmail author |
| |
Institution: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 201 N. Goodwin Avenue, Urbana, IL 61801-2302, USA;(2) Department of Computer Science, University of Iowa, Iowa City, IA 52242-1419, USA |
| |
Abstract: | Let $P$ be a set of $n$ points in $\Re^d$. The {\em
radius} of a $k$-dimensional flat ${\cal F}$ with
respect to $P$, which we denote by ${\cal RD}({\cal F},P)$,
is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where
$\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between
$p$ and its projection onto ${\cal F}$. The $k$-flat
radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the
minimum, over all $k$-dimensional flats ${\cal F}$, of
${\cal RD}({\cal F},P)$. We consider the problem of
computing ${R^{\rm 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 < \eps \leq 1$, returns a
$k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 +
\eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd
C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that
depends only on $\eps$ 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/\eps^c)}$, where $c$ is an appropriate constant. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|