Manifold reconstruction from point samples

Siu Wing Cheng; Tamal K. Dey; Edgar A. Ramos

Manifold reconstruction from point samples

Siu Wing Cheng^*, Tamal K. Dey, Edgar A. Ramos

^*Corresponding author for this work

Department of Computer Science and Engineering

Research output: Contribution to conference › Conference Paper › peer-review

91 Citations (Scopus)

Abstract

We present an algorithm to "reconstruct" a smooth k-dimensional manifold M embedded in an Euclidean space ℝ^d from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).

Original language	English
Pages	1018-1027
Number of pages	10
Publication status	Published - 2005
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: 23 Jan 2005 → 25 Jan 2005

Conference

Conference	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	23/01/05 → 25/01/05

Cite this

@conference{c9c21ce760da4fe487716c2639297927,

title = "Manifold reconstruction from point samples",

abstract = "We present an algorithm to {"}reconstruct{"} a smooth k-dimensional manifold M embedded in an Euclidean space ℝd from a {"}sufficiently dense{"} point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).",

author = "Cheng, \{Siu Wing\} and Dey, \{Tamal K.\} and Ramos, \{Edgar A.\}",

year = "2005",

language = "English",

pages = "1018--1027",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - Manifold reconstruction from point samples

AU - Cheng, Siu Wing

AU - Dey, Tamal K.

AU - Ramos, Edgar A.

PY - 2005

Y1 - 2005

N2 - We present an algorithm to "reconstruct" a smooth k-dimensional manifold M embedded in an Euclidean space ℝd from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).

AB - We present an algorithm to "reconstruct" a smooth k-dimensional manifold M embedded in an Euclidean space ℝd from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).

UR - https://www.scopus.com/pages/publications/20744446730

M3 - Conference Paper

AN - SCOPUS:20744446730

SP - 1018

EP - 1027

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

Manifold reconstruction from point samples

Abstract

Conference

Other files and links

Fingerprint

Cite this