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

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

doi:10.1145/1247069.1247135

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Pages	381-389
Number of pages	9
DOIs	https://doi.org/10.1145/1247069.1247135
State	Published - 2007
Event	23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of Duration: Jun 6 2007 → Jun 8 2007

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	23rd Annual Symposium on Computational Geometry, SCG'07
Country/Territory	Korea, Republic of
City	Gyeongju
Period	6/6/07 → 6/8/07

Keywords

Dimensionality reduction
Doubling dimension
Moving points
Random projection

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Online availability

10.1145/1247069.1247135

Library availability

Discover UIUC Full Text

Cite this

Embeddings of surfaces, curves, and moving points in euclidean space. / Agarwal, Pankaj K.; Har-Peled, Sariel; Yu, Hai.
Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07. 2007. p. 381-389 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Agarwal, PK, 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. Proceedings of the Annual Symposium on Computational Geometry, pp. 381-389, 23rd Annual Symposium on Computational Geometry, SCG'07, Gyeongju, Korea, Republic of, 6/6/07. https://doi.org/10.1145/1247069.1247135

@inproceedings{c96f62b26d404f31a3bbe6f30b31d7bf,

title = "Embeddings of surfaces, curves, and moving points in euclidean space",

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.",

keywords = "Dimensionality reduction, Doubling dimension, Moving points, Random projection",

author = "Agarwal, {Pankaj K.} and Sariel Har-Peled and Hai Yu",

year = "2007",

doi = "10.1145/1247069.1247135",

language = "English (US)",

isbn = "1595937056",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "381--389",

booktitle = "Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07",

}

TY - GEN

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

AU - Agarwal, Pankaj K.

AU - Har-Peled, Sariel

AU - Yu, Hai

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 -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this