Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-2005-1-008

Cycle bases of graphs and sampled manifolds

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

MPI-I-2005-1-008. February 2005, 30 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2005-1-008.ps1563 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2005-1-008
Hide details for BibTeXBibTeX
@TECHREPORT{GotsmanKaligosiMehlhornMichailPyrga,
  AUTHOR = {Gotsman, Craig and Kaligosi, Kanela and Mehlhorn, Kurt and Michail, Dimitrios and Pyrga, Evangelia},
  TITLE = {Cycle bases of graphs and sampled manifolds},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2005-1-008},
  MONTH = {February},
  YEAR = {2005},
  ISSN = {0946-011X},
}