Delaunay simplices in diagonally distorted lattices

DOI10.1016/J.COMGEO.2019.01.010MaRDI QIDQ2331209zbMATH OpenOpenAlexWikidataFDO

Authors Aruni Choudhary, Arijit Ghosh

Publication date 25 October 2019

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.07024

zbMATH Keywords

Delaunay triangulationmesh qualitypermutahedral latticeprotection of lattices

Mathematics Subject Classification ID

Inequalities and extremum problems involving convexity in convex geometry (52A40) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Abstract: Delaunay protection is a measure of how far a Delaunay triangulation is 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 $mathbb{R}^d$. 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.

Review text

The authors consider a family of lattices \(T_\delta(\mathbb{Z}^d)\) in \(\mathbb{R}^d\) obtained by squeezing \(\mathbb{Z}^d\) in direction \((1,\ldots,1)\). They determine the following three geometric quantities in dependence of the parameter \(0<\delta\le 1\) and show that they are maximized for \(\delta=1/\sqrt{d+1}\): The \textit{normalized protection} \(\mathcal{P}_\delta/R_\delta\) is the quotient of the \textit{protection} \(\mathcal{P}_\delta\), which denotes the largest \(\alpha\) such that the radius of the circumball of every simplex \(\sigma\) of the Delaunay triangulation of \(T_\delta(\mathbb{Z}^d)\) can be enlarged by \(\alpha\) such that it still contains no other points from \(T_\delta(\mathbb{Z}^d)\) but the vertices of \(\sigma\), and the \textit{Delaunay radius} \(R_\delta\), which is the circumradius of the Delaunay simplices. The \textit{thickness} \(\Theta_\delta\) is the quotient of minimal height and diameter of the Delaunay simplices. The \textit{aspect ratio} \(\Gamma_\delta\) is the quotient of minimal height and the diameter of the circumballs of the Delaunay simplices.

Recommendations

• Lattice Delone simplices with super-exponential volume
• Covering and packing with spheres by diagonal distortion in R^n
• Diameter series of lattice covering simplices
• Tight stretch factors for L₁- and L_-Delaunay triangulations
• Infinite serie of extreme Delaunay polytopes

Cites work

• A probabilistic approach to reducing algebraic complexity of Delaunay triangulations
• Anisotropic Delaunay mesh generation
• Anisotropic Delaunay meshes of surfaces
• Anisotropic triangulations via discrete Riemannian Voronoi diagrams
• Computational geometry. Algorithms and applications.
• Covering and packing with spheres by diagonal distortion in R^n
• Delaunay mesh generation.
• Delaunay stability via perturbations
• Dual complexes of cubical subdivisions of \({\mathbb{R}}^{n}\)
• Generating well-shaped \(d\)-dimensional Delaunay meshes.
• Geometric and topological inference
• On the optimality of the FCC lattice for soft sphere packing
• Only distances are required to reconstruct submanifolds
• Power Diagrams: Properties, Algorithms and Applications
• Silver exudation
• Simplizialzerlegungen von beschränkter Flachheit
• Smoothing and cleaning up slivers
• Some Combinatorial Lemmas in Topology
• The stability of Delaunay triangulations

Cited in

(4)

• Delaunay polytopes of cut lattices
• Coxeter triangulations have good quality
• Delaunay polytopes derived from the Leech lattice
• Solutions to the Minimum Variance Problem Using Delaunay Triangulation

This page was built for publication: Delaunay simplices in diagonally distorted lattices

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