Abstract
We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space Rd. We assume that M is known to us only through a finite sample P \subset M, as is often the case in applications. The adaptive neighborhood graph is a geometric graph on P. Its complexity is at most \min{2^{O(k)n, n2}, where n = |P| and k = dim M, as opposed to the n\lceil d/2 \rceil complexity of the Delaunay triangulation, which is often used to model manifolds. We prove that we can correctly infer the connected components 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(k^{7} 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Giesen, J., Wagner, U. Shape Dimension and Intrinsic Metric from Samples of Manifolds. Discrete Comput Geom 32, 245–267 (2004). https://doi.org/10.1007/s00454-004-1120-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-004-1120-8