TY - GEN
T1 - Embeddings of surfaces, curves, and moving points in euclidean space
AU - Agarwal, Pankaj K.
AU - Har-Peled, Sariel
AU - Yu, Hai
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Dimensionality reduction
KW - Doubling dimension
KW - Moving points
KW - Random projection
UR - http://www.scopus.com/inward/record.url?scp=35348892607&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35348892607&partnerID=8YFLogxK
U2 - 10.1145/1247069.1247135
DO - 10.1145/1247069.1247135
M3 - Conference contribution
AN - SCOPUS:35348892607
SN - 1595937056
SN - 9781595937056
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 381
EP - 389
BT - Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
T2 - 23rd Annual Symposium on Computational Geometry, SCG'07
Y2 - 6 June 2007 through 8 June 2007
ER -