Preliminary versionA preliminary version of these results was presented in: Tamal K. Dey and Sumanta Guha. Algorithms for manifolds and simplicial complexes in Euclidean 3-space (preliminary version). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 398-407, Philadelphia, Pennsylvania, 22-24 May 1996.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
General Terms: Algorithms, Theory
Additional Key Words and Phrases: $d$ dimensions, generators, homology, homotopy, simplicial complexes, topology
Selected references
- Tamal K. Dey and Sumanta Guha. Optimal algorithms for curves on surfaces. In 36th Annual Symposium on Foundations of Computer Science, pages 266-274, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Joel Friedman. Computing Betti numbers via combinatorial Laplacians. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 386-391, Philadelphia, Pennsylvania, 22-24 May 1996.
- Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499-507, November 1979.