Centroidal Voronoi Tessellation vs. Optimal Delaunay Triangulation

Wenping Wang, Department of Computer Science at The University of Hong Kong

We present a comparative study on CVT (Centroidal Voronoi Tessellation) and ODT (Optimal Delaunay Triangulation), which are two closely related optimization-based methods for mesh generation. While CVT is relatively well understood and widely applied, ODT has only recently been proposed as a promising alternative to CVT for quality mesh generation. In the first part of this talk, we briefly introduce CVT and discuss its applications to mesh generation, circle packing, and minimal surface modeling. In the second part, we examine numerical evidence that establishes the superiority of ODT over CVT in suppressing slivers in tetrahedral meshes. Then, we propose a global optimization scheme to improve the efficiency and robustness of ODT computation and an extended ODT formulation for the generation of graded tetrahedral meshes. Throughout, emphasis is placed on comparing CVT and ODT in terms of their formulations, properties, computations, and applications.