An incremental algorithm for Betti numbers of simplicial complexes

ABSTRACT

A general and direct method for computing the betti numbers of the homology groups of a finite simplicial complex is given. For subcomplexes of a triangulation of S³ this method has implementations that run in time O(n&dgr;(n)) and O(n), where n is the number of simplices in the triangulation. If applied to the family of &dgr;-shapes of a finite point set in R³ it takes time O(n&dgr;(n)) to compute the betti numbers of all &dgr;-shapes.

REFERENCES

• 1: P. Alexandroff and H. Hopf. Topologie L Julius Springer, Berlin, 1935.
• 2: Marshall Bern, Compatible tetrahedralizations, Proceedings of the ninth annual symposium on Computational geometry, p.281-288, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161151]
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Bruce Randall Donald , David Renpan Chang, On the complexity of computing the homology type of a triangulation, Proceedings of the 32nd annual symposium on Foundations of computer science, p.650-661, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185432]
• 5: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 6: Herbert Edelsbrunner, Weighted alpha shapes, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 7: H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Inform. Theory IT-29 (1983), 551-559.
• 8: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 9: P. J. Giblin. Graphs, Surfaces, and Homolog~t. Seco~.d edition, Chapman and Hall, London, 1981.
• 10: R. Kannan and A. Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of ~z integer matrix. SIAM Y. Comput. 8 (1979), 499-507
• 11: J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Redwood City, California, 1984.
• 12: J. J. Rotman. An Introduction to Algebraic Topolog~t. Springer-Verlag, New York, 1988.
• 13: H. J. Smith. On systems of indeterminate equations and congruences. Philos. Trans. 151 (1861), 293-32(;.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Verification