Cycle bases of graphs and sampled manifolds

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

doi:10.1016/j.cagd.2006.07.001

Cycle bases of graphs and sampled manifolds

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

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Point samples of a surface in R³ 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 language	English (US)
Pages (from-to)	464-480
Number of pages	17
Journal	Computer Aided Geometric Design
Volume	24
Issue number	8-9
DOIs	https://doi.org/10.1016/j.cagd.2006.07.001
State	Published - Nov 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

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

Access to Document

10.1016/j.cagd.2006.07.001

Cite this

@article{7f55c37be93e4e82863be5bf8eed65ee,

title = "Cycle bases of graphs and sampled manifolds",

abstract = "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.",

keywords = "Cycle basis, Homology basis, Manifold, Nearest neighbor graph, Non-trivial and trivial loops, Sample points",

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

year = "2007",

month = nov,

doi = "10.1016/j.cagd.2006.07.001",

language = "English (US)",

volume = "24",

pages = "464--480",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier",

number = "8-9",

}

TY - JOUR

T1 - Cycle bases of graphs and sampled manifolds

AU - Gotsman, Craig

AU - Kaligosi, Kanela

AU - Mehlhorn, Kurt

AU - Michail, Dimitrios

AU - Pyrga, Evangelia

PY - 2007/11

Y1 - 2007/11

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

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

KW - Cycle basis

KW - Homology basis

KW - Manifold

KW - Nearest neighbor graph

KW - Non-trivial and trivial loops

KW - Sample points

UR - http://www.scopus.com/inward/record.url?scp=35248851109&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248851109&partnerID=8YFLogxK

U2 - 10.1016/j.cagd.2006.07.001

DO - 10.1016/j.cagd.2006.07.001

M3 - Article

AN - SCOPUS:35248851109

SN - 0167-8396

VL - 24

SP - 464

EP - 480

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

IS - 8-9

ER -

Cycle bases of graphs and sampled manifolds

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this