Dual complexes of cubical subdivisions of \({\mathbb{R}}^{n}\) (Q664353)

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.