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