Shape dimension and intrinsic metric from samples of manifolds with high co-dimension

J. Giesen, U. Wagner, in:, ACM, 2003, pp. 329–337.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
;
Abstract
We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some (potentially very high-dimensional) Euclidean space ℝd. We assume that M is known to us only through a finite sample P ⊂ M, as it is often the case in applications. The adaptive neighborhood graph is a geometric graph on P. Its complexity is at most min{2O(k)(n, n2}, where n = |P| and k = dim M, as opposed to the n⌈d/2⌉ complexity of the Delaunay triangulation, which is often used to model manifolds. We show that we can provably correctly infer the connectivity of M and the dimension of M from the adaptive neighborhood graph provided a certain standard sampling condition is fulfilled. The running time of the dimension detection algorithm is d2O(k7 log k) for each connected component of M. If the dimension is considered constant, this is a constant-time operation, and the adaptive neighborhood graph is of linear size. Moreover, the exponential dependence of the constants is only on the intrinsic dimension k, not on the ambient dimension d. This is of particular interest if the co-dimension is high, i.e., if k is much smaller than d, as is the case in many applications. The adaptive neighborhood graph also allows us to approximate the geodesic distances between the points in P.
Publishing Year
Date Published
2003-06-01
Page
329 - 337
Conference
SoCG: Symposium on Computational Geometry
IST-REx-ID

Cite this

Giesen J, Wagner U. Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. In: ACM; 2003:329-337. doi:10.1145/777792.777841
Giesen, J., & Wagner, U. (2003). Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (pp. 329–337). Presented at the SoCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/777792.777841
Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric from Samples of Manifolds with High Co-Dimension,” 329–37. ACM, 2003. https://doi.org/10.1145/777792.777841.
J. Giesen and U. Wagner, “Shape dimension and intrinsic metric from samples of manifolds with high co-dimension,” presented at the SoCG: Symposium on Computational Geometry, 2003, pp. 329–337.
Giesen J, Wagner U. 2003. Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. SoCG: Symposium on Computational Geometry 329–337.
Giesen, Joachim, and Uli Wagner. Shape Dimension and Intrinsic Metric from Samples of Manifolds with High Co-Dimension. ACM, 2003, pp. 329–37, doi:10.1145/777792.777841.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar