Show simple item record

dc.contributor.authorDonald, Bruce Randallen_US
dc.contributor.authorChang, David Renpanen_US
dc.date.accessioned2007-04-23T17:51:41Z
dc.date.available2007-04-23T17:51:41Z
dc.date.issued1990-08en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1183en_US
dc.identifier.urihttps://hdl.handle.net/1813/7023
dc.description.abstractWe 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.en_US
dc.format.extent4079950 bytes
dc.format.extent830528 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn Computing the Homology Type of a Triangulationen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics