On the sizes of Delaunay meshes

DOI10.1016/J.COMGEO.2005.08.002MaRDI QIDQ2489538zbMATH OpenOpenAlexFDO

Authors Siu-Wing Cheng

Publication date 28 April 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL http://repository.ust.hk/ir/bitstream/1783.1-2600/1/delsize.pdf

zbMATH Keywords

Aspect ratioDelaunay triangulationGradednessMesh generationRadius-edge ratio

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Let \(\mathcal P\) be a polyhedral domain occupying a convex volume. We prove that the size of a graded mesh of \(\mathcal P\) with bounded vertex degree is within a factor \(O(H^3_{\mathcal P})\) of the size of any Delaunay mesh of \(\mathcal P\) with bounded radius-edge ratio. The term \(H_{\mathcal P}\) depends on the geometry of \(\mathcal P\) and it is likely a small constant when the boundaries of \(\mathcal P\) are fine triangular meshes. There are several consequences. First, among all Delaunay meshes with bounded radius-edge ratio, those returned by Delaunay refinement algorithms have asymptotically optimal sizes. This is another advantage of meshing with Delaunay refinement algorithms. Second, if no input angle is acute, the minimum Delaunay mesh with bounded radius-edge ratio is not much smaller than any minimum mesh with aspect ratio bounded by a particular constant.

Recommendations

• scientific article; zbMATH DE number 2079352
• Delaunay refinement algorithms for triangular mesh generation
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Three-dimensional Delaunay mesh generation
• A 2D advancing-front Delaunay mesh refinement algorithm

Cites work

• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Generating well-shaped Delaunay meshes in 3D
• Geometry and topology for mesh generation
• scientific article; zbMATH DE number 1263247 (Why is no real title available?)
• scientific article; zbMATH DE number 2079352 (Why is no real title available?)
• On the Radius-Edge Condition in the Control Volume Method
• Quality Mesh Generation in Higher Dimensions
• Quality meshing for polyhedra with small angles
• Quality Meshing with Weighted Delaunay Refinement
• Silver exudation
• WHEN AND WHY DELAUNAY REFINEMENT ALGORITHMS WORK

Cited in

(4)

• scientific article; zbMATH DE number 2079352 (Why is no real title available?)
• Size complexity of volume meshes vs. surface meshes
• ON 2D SOLID α-COMPLEXES OF POISSON DISC SAMPLINGS
• Quality meshing for polyhedra with small angles

This page was built for publication: On the sizes of Delaunay meshes

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