Math @ Duke

Publications [#235495] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Yu, H, Embeddings of surfaces, curves, and moving points in euclidean space,
Proceedings of the Annual Symposium on Computational Geometry
(2007),
pp. 381389 [doi]
(last updated on 2017/12/14)
Abstract: In this paper we show that dimensionality reduction (i.e., JohnsonLindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally between lowdimensional 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. Copyright 2007 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

