Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: On Computing the Homology Type of a Triangulation
Authors: Donald, Bruce Randall
Chang, David Renpan
Keywords: computer science
technical report
Issue Date: Aug-1990
Publisher: Cornell University
Abstract: We analyze an algorithm for computing the homology type of a triangulation. By triangulation, we mean a finite simplicial complex; its homology type is given by its homology groups (with integer coefficients). The algorithm could be used in computer-aided design to tell whether two finite-element meshes or Bezier-spline surfaces are of the same "topological type," and whether they can be embedded in $\Re^{3}$. Homology computation is a purely combinatorial problem of considerable intrinsic interest. While the worst-case bounds we obtain for this algorithm are poor, we argue that many triangulations (in general) and virtually all triangulations in design are very "sparse," in a sense we make precise. We formalize this sparseness measure, and perform a probabilistic analysis of the sparse case to show that the expected running time of the algorithm is roughly quadratic in the geometric complexity (number of simplices) and linear in the dimension.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1183.pdf3.98 MBAdobe PDFView/Open
90-1183.ps811.06 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us