de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Cycle bases of graphs and sampled manifolds

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44722

Kaligosi,  Kanela
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45040

Michail,  Dimitrios
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45230

Pyrga,  Evangelia
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-2005-1-008.ps
(Any fulltext), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Gotsman, C., Kaligosi, K., Mehlhorn, K., Michail, D., & Pyrga, E.(2005). Cycle bases of graphs and sampled manifolds (MPI-I-2005-1-008). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-684C-E
Abstract
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.