---
_id: '2426'
abstract:
- lang: eng
text: We introduce the adaptive neighborhood graph as a data structure for modeling
a smooth manifold M embedded in some Euclidean space ℝ d. We assume that M is
known to us only through a finite sample P ⊂ M, as 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 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 d20(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.
author:
- first_name: Joachim
full_name: Giesen, Joachim
last_name: Giesen
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Giesen J, Wagner U. Shape dimension and intrinsic metric from samples of manifolds.
*Discrete & Computational Geometry*. 2004;32(2):245-267. doi:10.1007/s00454-004-1120-8
apa: Giesen, J., & Wagner, U. (2004). Shape dimension and intrinsic metric from
samples of manifolds. *Discrete & Computational Geometry*, *32*(2),
245–267. https://doi.org/10.1007/s00454-004-1120-8
chicago: 'Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric
from Samples of Manifolds.” *Discrete & Computational Geometry* 32, no.
2 (2004): 245–67. https://doi.org/10.1007/s00454-004-1120-8.'
ieee: J. Giesen and U. Wagner, “Shape dimension and intrinsic metric from samples
of manifolds,” *Discrete & Computational Geometry*, vol. 32, no. 2, pp.
245–267, 2004.
ista: Giesen J, Wagner U. 2004. Shape dimension and intrinsic metric from samples
of manifolds. Discrete & Computational Geometry. 32(2), 245–267.
mla: Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric from
Samples of Manifolds.” *Discrete & Computational Geometry*, vol. 32,
no. 2, Springer, 2004, pp. 245–67, doi:10.1007/s00454-004-1120-8.
short: J. Giesen, U. Wagner, Discrete & Computational Geometry 32 (2004) 245–267.
date_created: 2018-12-11T11:57:35Z
date_published: 2004-09-01T00:00:00Z
date_updated: 2019-04-26T07:22:12Z
day: '01'
doi: 10.1007/s00454-004-1120-8
extern: 1
intvolume: ' 32'
issue: '2'
month: '09'
page: 245 - 267
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '4499'
quality_controlled: 0
status: public
title: Shape dimension and intrinsic metric from samples of manifolds
type: journal_article
volume: 32
year: '2004'
...