Embeddings of Surfaces, Curves, and Moving Points in Euclidean Space
Pankaj K. Agarwal,
Sariel Har-Peled,
and Hai Yu.
In this paper we show that dimensionality reduction (i.e.,
Johnson-Lindenstrauss lemma) preserves not only the distances
between static points, but also between moving points, and more
generally between low-dimensional flats, polynomial curves, curves
with low winding degree, and polynomial surfaces.
%
We also show that surfaces with bounded doubling dimension can be
embedded into low dimension with small additive error. Finally,
we show that for points with polynomial motion, the radius of the
smallest enclosing ball can be preserved under dimensionality
reduction.
PDF /
PSSlides
[source].
Last modified: Sat Jun 9 01:52:56 CDT 2007