Cycle bases of graphs and sampled manifolds

Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Point samples of a surface in R3 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.

Original languageEnglish (US)
Pages (from-to)464-480
Number of pages17
JournalComputer Aided Geometric Design
Issue number8-9
StatePublished - Nov 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design


  • Cycle basis
  • Homology basis
  • Manifold
  • Nearest neighbor graph
  • Non-trivial and trivial loops
  • Sample points


Dive into the research topics of 'Cycle bases of graphs and sampled manifolds'. Together they form a unique fingerprint.

Cite this