Abstract
We propose an entropy function for simplicial complices. Its value gives the expected cost of the optimal encoding of sequences of vertices of the complex, when any two vertices belonging to the same simplex are indistinguishable. We focus on the computational properties of the entropy function, showing that it can be computed efficiently. Several examples over complices consisting of hundreds of simplices show that the proposed entropy function can be used in the analysis of large sequences of simplicial complices that often appear in computational topology applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Attali, D., Lieutier, A., Salinas, D.: Efficient data structure for representing and simplifying simplicial complexes in high dimensions. Int. J. Comput. Geom. Appl. 22(04), 279–303 (2012)
Ay, N., Olbrich, E., Bertschinger, N., Jost, J.: A geometric approach to complexity. Chaos 21(3), 22 (2011)
Csiszár, I., Körner, J., Lovász, L., Marton, K., Simonyi, G.: Entropy splitting for antiblocking corners and perfect graphs. Combinatorica 10(1), 27–40 (1990)
Dantchev, S., Ivrissimtzis, I.: Efficient construction of the Čech complex. Comput. Graph. 36(6), 708–713 (2012)
de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebraic Geom. Topol. 7, 339–358 (2007)
de Silva, V., Carlsson, G.: Topological estimation using witness complexes. In: Alexa, M., Rusinkiewicz, S. (eds.) Eurographics Symposium on Point-Based Graphics. ETH, Zürich (2004)
Edelsbrunner, H.: The union of balls and its dual shape. Discrete Comput. Geom. 13(1), 415–440 (1995)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: FOCS 2000, p. 454. IEEE (2000)
Guibas, L.J., Oudot, S.Y.: Reconstruction using witness complexes. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 1076–1085, Philadelphia, PA, USA. SIAM (2007)
Korner, J., Marton, K.: New bounds for perfect hashing via information theory. Eur. J. Comb. 9(6), 523–530 (1988)
Körner, J.: Coding of an information source having ambiguous alphabet and the entropy of graphs. In: 6th Prague Conference on Information Theory, pp. 411–425 (1973)
Simonyi, G.: Graph entropy: a survey. Comb. Optim. 20, 399–441 (1995)
Vejdemo-Johansson, M.: Interleaved computation for persistent homology. CoRR, abs/1105.6305 (2011)
Wales, D.J., Ulker, S.: Structure and dynamics of spherical crystals characterized for the Thomson problem. Phys. Rev. B 74(21), 212101 (2006)
Zomorodian, A.: Fast construction of the Vietoris-Rips complex. Comput. Graph. 34, 263–271 (2010)
Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2005)
Acknowledgement
This research was partially supported by the EPRSC Grant EP/K016687/1 “Topology, Geometry and Laplacians of Simplicial Complexes”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Dantchev, S., Ivrissimtzis, I. (2017). Simplicial Complex Entropy. In: Floater, M., Lyche, T., Mazure, ML., Mørken, K., Schumaker, L. (eds) Mathematical Methods for Curves and Surfaces. MMCS 2016. Lecture Notes in Computer Science(), vol 10521. Springer, Cham. https://doi.org/10.1007/978-3-319-67885-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-67885-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67884-9
Online ISBN: 978-3-319-67885-6
eBook Packages: Computer ScienceComputer Science (R0)