Delaunay simplices in diagonally distorted lattices

Aruni Choudhary, Arijit Ghosh

Introduction

In numerical simulations and finite element analysis, the quality of the underlying simplicial mesh is paramount. "Skinny" simplices—those with small heights relative to their edge lengths—often introduce numerical instability and significant errors. While the standard integer grid ($\mathbb{Z}^d$) is a common starting point, it is inherently degenerate for Delaunay triangulations, as multiple points frequently lie on the same circumsphere. This paper explores a systematic approach to resolving this degeneracy through diagonal distortion.

Methodology: Diagonally Distorted Lattices

The authors analyze a family of lattices generated by a transformation $T_\delta$, which stretches the integer grid along its principal diagonal $(1, 1, \dots, 1)$. The degree of stretching is controlled by a parameter $\delta \in [0, 1]$. To partition these lattices into simplices, the Freudenthal triangulation is employed, providing a consistent way to subdivide the distorted hypercubes.

The Freudenthal triangulation of a unit cube, providing the base simplicial structure for the distorted lattice.

The resulting meshes are evaluated using three key quality metrics:

  1. Thickness ($\Theta$): The ratio of the minimum height of a simplex to its maximum edge length.
  2. Aspect Ratio ($\Gamma$): The ratio of the minimum height to the diameter of the circumsphere.
  3. Protection ($\alpha$): A measure of stability quantifying the distance from degeneracy; specifically, the extent to which a simplex's circumball can be expanded before encountering another lattice point.

The Permutahedral Optimum

The central finding of the study is the identification of a "sweet spot" for lattice distortion. When the parameter $\delta$ is set to $1/\sqrt{d+1}$, the distorted grid becomes isometric to the permutahedral lattice ($A^*_d$).

Remarkably, all three quality measures—protection, thickness, and aspect ratio—are simultaneously maximized at this exact point. This suggests that the permutahedral lattice is not just a convenient geometric structure but a fundamentally optimal one for simplicial meshing within this family of distortions.

Quality measures across dimensions 3 to 8, showing clear peaks at the optimal distortion parameter corresponding to the permutahedral lattice.

Dimensional Scaling and Stability

The paper provides closed-form expressions for these metrics, allowing for an analysis of how mesh quality scales with dimension $d$. For instance, the normalized protection of the optimal lattice is shown to scale as $O(1/d^2)$. This explicit scaling provides a roadmap for researchers working in high-dimensional geometric computing, offering a predictable measure of the trade-offs involved as complexity increases.

Conclusion

By formalizing the relationship between diagonal distortion and simplicial quality, this work provides a rigorous theoretical foundation for using permutahedral lattices in high-quality mesh generation. The simultaneous optimization of multiple geometric metrics at a single distortion point underscores the unique suitability of this lattice for stable numerical computation.

Summary updated

Abstract

Delaunay protection is a measure of how far is a Delaunay triangulation from being degenerate. In this short paper we study the protection properties and other quality measures of the Delaunay triangulations of a family of lattices that is obtained by distorting the integer grid in Rd<math><msup is="true"><mrow is="true"><mi mathvariant="double-struck" is="true">R</mi></mrow><mrow is="true"><mi is="true">d</mi></mrow></msup></math>. We show that the quality measures of this family are maximized for a certain distortion parameter, and that for this parameter, the lattice is isometric to the permutahedral lattice, which is a well-known object in discrete geometry.
BibTeX
@article{choudhary2019delaunay,
  author = {Aruni Choudhary and Arijit Ghosh},
  title = {{Delaunay simplices in diagonally distorted lattices}},
  journal = {Comput. Geom},
  year = {2019},
  doi = {10.1016/j.comgeo.2019.01.010},
}
Figure