Embeddings of surfaces, curves, and moving points in euclidean space

Published

Journal Article

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. © 2013 Society for Industrial and Applied Mathematics.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Har-Peled, S; Yu, AH

Published Date

  • July 18, 2013

Published In

Volume / Issue

  • 42 / 2

Start / End Page

  • 442 - 458

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/110830046

Citation Source

  • Scopus