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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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)
Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Pages381-389
Number of pages9
DOIs
StatePublished - Oct 22 2007
Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
Duration: Jun 6 2007Jun 8 2007

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other23rd Annual Symposium on Computational Geometry, SCG'07
CountryKorea, Republic of
CityGyeongju
Period6/6/076/8/07

Keywords

  • Dimensionality reduction
  • Doubling dimension
  • Moving points
  • Random projection

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

  • Cite this

    Agarwal, P. K., Har-Peled, S., & Yu, H. (2007). Embeddings of surfaces, curves, and moving points in euclidean space. In Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07 (pp. 381-389). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1247069.1247135