Dual complexes of cubical subdivisions of R^n

DOI10.1007/S00454-011-9382-4MaRDI QIDQ664353zbMATH OpenOpenAlexFDO

Authors Herbert Edelsbrunner, Michael Kerber

Publication date 1 March 2012

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-011-9382-4

zbMATH Keywords

(Hierarchical) cubical subdivisionsCountingDistortionFreudenthal triangulationGeometric realizationSimplicial complexes

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) PL-topology (57Q99) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Discretization is essential both in theory and in practice. Cubical decompositions of objects arise quite naturally in the digital environment, while simplicial ones are often preferred for theoretical reasons (e.g. for computing persistent homology [\textit{P. Bendich}, \textit{H. Edelsbrunner} and \textit{M. Kerber}, IEEE Trans. Vis. Comput. Graph. 16, 1251--1260 (2010)]). The present paper proposes standard procedures for building a convenient simplicial complex out of a cubical structure. A classical construction is the Delaunay triangulation, but in the case of a very regular grid of points like the one of vertices in the cubical structures of interest, this triangulation is degenerate and not uniquely determined. So the authors introduce a clever distorsion which stabilizes the triangulation, obtained as nerve of the set of Voronoi cells of the vertices. This turns out to be built by translated copies of the Freudenthal triangulation [\textit{H. Freudenthal}, Ann. Math. (2) 43, 580--582 (1942; Zbl 0060.40701)] of the cube. Another approach is by taking the nerve of the set of cubical cells themselves. The authors consider this dual construction for what they call \textit{hierarchical} cubical subdivisions of \(\mathbb{R}^n\), a generalization of quad-trees and oct-trees [\textit{H. Samet}, The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading (1990)]; [\textit{M. Sonka}, \textit{V. Hlavac} and \textit{R. Boyle}, Image Processing, Analysis and Machine Vision, 2nd edn. PWS, Pacific Grove (1999)]. Once more a (suitably small) distortion is necessary, since the regularity of the subdivision would cause a dimensional explosion of the nerve. To grant the geometric realization in \(\mathbb{R}^n\) of this \textit{dual} complex, the construction is limited (without actual loss of generality) to hierarchical cubical structures in which the ratio between the edge lengths of neighbouring cells is either 1 or 2.

Recommendations

• The cubical cohomology ring: an algorithmic approach
• Weakly well-composed cell complexes over nD pictures
• Complexity of projected images of convex subdivisions
• Subdivision of maps of digital images
• Well-composed cell complexes

Cites work

• Computational geometry. Algorithms and applications.
• Computational homology
• Computational topology. An introduction
• Coreduction homology algorithm for regular CW-complexes
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• Provably good mesh generation
• Simplizialzerlegungen von beschränkter Flachheit
• Some Combinatorial Lemmas in Topology

Cited in

(7)

• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Delaunay simplices in diagonally distorted lattices
• Covering and packing with spheres by diagonal distortion in R^n
• The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups
• On the optimality of the FCC lattice for soft sphere packing
• Solutions to the Minimum Variance Problem Using Delaunay Triangulation
• Surface-based computation of the Euler characteristic in the BCC grid

This page was built for publication: Dual complexes of cubical subdivisions of \({\mathbb{R}}^{n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q664353)