Optimal Delaunay Triangulations

Optimal Delaunay triangulations (ODTs) are optimal meshes minimizing the inter- polation error to a convex function in Lp norm. We shall present several application of ODT.

1. Mesh smoothing. Meshes with high quality are obtained by minimizing the interpolation error in a weighted L1 norm.

2. Anisotropic mesh adaptation. Optimal anisotropic interpolation error estimate is obtained by choosing anisotropic functions. The error estimate is used to produce anisotropic mesh adaptation for convection-dominated problems.

3. Sphere covering and convex polytope approximation. Asymptotic exact and sharp estimate of some constant in these two problems are obtained from ODT.

4. Quantization. Optimization algorithms based on ODT are applied to quantization to speed up the processing.