Abstract
We use a distortion to define the dual complex of a cubical subdivision of ℝn as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝn.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexandroff, P., Hopf, H.: Topologie I. Springer, Berlin (1935)
Bendich, P., Edelsbrunner, H., Kerber, M.: Computing robustness and persistence for images. IEEE Trans. Vis. Comput. Graph. 16, 1251–1260 (2010)
Bern, M., Eppstein, D., Gilbert, J.: Provably good mesh generation. J. Comput. Syst. Sci. 48, 384–409 (1994)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry. Algorithms and Applications, 3rd edn. Springer, Berlin (2008)
Dlotko, P., Kaczyński, T., Mrozek, M., Wanner, T.: Coreduction homology algorithm for regular CW-complexes. Discrete Comput. Geom. 46, 361–388 (2011)
Edelsbrunner, H., Harer, J.L.: Computational Topology. An Introduction. Am. Math. Soc., Providence (2010)
Freudenthal, H.: Simplizialzerlegung von beschränkter Flachheit. Ann. Math. 43, 580–582 (1942)
Fuchs, R., Hauser, H.: Visualization of multi-variate scientific data. Comput. Graph. Forum 28, 1670–1690 (2009)
Johnson, C.: Top scientific visualization research problems. IEEE Comput. Graph. Appl. 24, 13–17 (2004)
Kaczyński, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, New York (2004)
Kuhn, H.W.: Some combinatorial lemmas in topology. IBM J. Res. Dev. 45, 518–524 (1960)
Moore, D.: The cost of balancing generalized quadtrees. In: Proc. 3rd ACM Symp. Solid Modeling Appl, pp. 305–312 (1995)
Munkres, J.R.: Elements of Algebraic Topology. Perseus, Cambridge (1984)
Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading (1990)
Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis and Machine Vision, 2nd edn. PWS, Pacific Grove (1999)
Stock, S.: High energy X-ray scattering quantification of bone strains. Talk at the First Workshop on “Bone Tissue: Hierarchical Simulations for Clinical Applications”, Los Angeles (2010)
Wagner, H., Chen, C., Vuçini, E.: Efficient computation of persistent homology for cubical data. In: Proc. 4th Workshop on Topology-based Methods in Data Analysis and Visualization (2011)
Weiss, K., De Floriani, L.: Diamond hierarchies of arbitrary dimension. Comput. Graph. Forum 28, 1289–1300 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Edelsbrunner, H., Kerber, M. Dual Complexes of Cubical Subdivisions of ℝn . Discrete Comput Geom 47, 393–414 (2012). https://doi.org/10.1007/s00454-011-9382-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-011-9382-4