Cycle bases of graphs and sampled manifolds
Point samples of a surface in R(3) are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the sample. We show that, under certain sampling conditions, the minimum cycle basis of a nearest neighbor graph of the sample encodes topological information about the surface and yields bases for the trivial and non-trivial loops of the surface. We validate our results by experiments. (C) 2007 Elsevier B.V. All rights reserved.
cycle basis homology basis manifold nearest neighbor graph non-trivial and trivial loops sample points