Dual Complexes of Cubical Subdivisions of ℝ n

Herbert Edelsbrunner, Michael KerberDiscret. Comput. Geom 2012 · OpenReview

Abstract

We use a distortion to define the dual complex of a cubical subdivision of ℝⁿ 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 ℝⁿ.

Introduction

Digital images and scientific data are typically represented as cubical grids—pixels in 2D and voxels in 3D. To optimize memory and computation, researchers often employ hierarchical structures like quad-trees or oct-trees, which use larger cubes for uniform regions and smaller cubes for areas requiring more detail.

However, many topological algorithms, such as computing persistent homology or generating smooth level sets, require a simplicial complex (a collection of triangles, tetrahedra, etc.). The standard conversion method involves "refinement," where each cube is subdivided into smaller simplices. This approach is computationally expensive and significantly inflates the number of elements in the mesh.

This paper proposes a "dual" approach: instead of splitting cubes, can we treat each cube center as a vertex and connect them? The primary challenge is ensuring that these simplices do not overlap or "fold" in ways that violate simplicial complex rules, particularly in higher dimensions (n ≥ 4).

Methods and the Distortion Trick

The authors' framework builds upon Freudenthal’s triangulation, a classic method for partitioning a single unit n-cube into n! simplices.

Freudenthal triangulation of a cube

To extend this to hierarchical subdivisions, the authors introduce a distortion transformation.

  1. The Distortion Trick: A small linear transformation ($T_\epsilon$) is applied to the integer grid, slightly "squashing" it along its main diagonal.
  2. Voronoi Nerve: By examining the Voronoi diagram of this distorted grid, the "dual complex" is defined as the nerve (intersection pattern) of these distorted cells. This distortion acts as a tie-breaker, ensuring the resulting triangulation is "generic" and well-defined.
Voronoi cell of an integer point after distortion in ℝ³
  1. Hierarchical Extension: This logic is extended to hierarchical grids where cubes vary in size. The authors define "fractually distorted cells" to manage boundaries between different-sized cubes.
  2. Geometric Realization: The core contribution is a topological proof showing that if the grid is balanced (adjacent cells' sizes differ by no more than a factor of 2), the abstract dual complex matches a physical drawing in ℝⁿ where vertices are placed at the original cube centers.

Key Insights and Results

  • Computational Efficiency: By connecting centers rather than refining every cube, the dual complex generally contains fewer simplices, offering a significant advantage for memory-intensive topological calculations.
  • The Role of Balance: The "balanced" condition, a common heuristic for mesh quality in computer science, is proven to be the exact mathematical requirement for a valid geometric realization in 3D and higher.
  • Dimensional Agnosticism: The framework is designed for ℝⁿ, making it applicable to 4D time-series data or complex multi-variate scientific datasets.
  • Triangulation Theorem: The distortion method is proven to perfectly select the Freudenthal triangulation for uniform grids.
  • Geometric Realization Theorem: For any balanced hierarchical cubical subdivision, the dual complex is a valid simplicial complex in ℝⁿ.

Limitations and Future Work

The authors identify a specific counterexample in 3D where an unbalanced subdivision (e.g., a very large cube adjacent to a very small one) causes the dual complex to self-intersect, rendering it unsuitable for geometric modeling. Additionally, while the proof relies on the hierarchical "tree" structure, it remains an open question whether the same realization holds for non-hierarchical but balanced subdivisions. Future work could also involve empirical performance comparisons of topological algorithms using these dual complexes versus standard cubical grids.

Summary updated

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.
BibTeX
@inproceedings{edelsbrunner2012dual,
  author = {Herbert Edelsbrunner and Michael Kerber},
  title = {{Dual Complexes of Cubical Subdivisions of ℝ n}},
  booktitle = {Discret. Comput. Geom},
  year = {2012},
  url = {https://openreview.net/forum?id=YMyZtTT6OF},
}
Figure