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

Pankaj K. Agarwal, Sariel Har-Peled, And Hai Yu

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)442-458
Number of pages17
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2013


  • Dimensionality reduction
  • Embeddings
  • Moving points
  • Random projection

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Embeddings of surfaces, curves, and moving points in euclidean space'. Together they form a unique fingerprint.

Cite this