Abstract: High quality isotropic meshing has been thoroughly studied in the past. Resulting techniques such as Optimal Delaunay Triangulation (ODT) and Centroidal Voronoi Tessellation (CVT) are well understood and widely used in a variety of applications. However, anisotropic meshing presents a considerably more difficult challenge. In this talk, we present anisotropic extensions of these high quality meshes. We first discuss the Generalized Optimal Delaunay Triangulation (GODT) that has been recently proposed by Long Chen based on functional approximation, before introducing a dual notion – Generalized Optimal Voronoi Tessellation. Both methods are variational in the sense that they are based on a minimization of the L1 norm of the functional approximation error. We provide a simple and efficient iterative algorithm for constructing GOVT using weighted CVT. Resulting cells are aligned with the hessian of a convex function that is being approximated. Finally, we prove a bound on the behavior of the error as the number of cells grows and suggest a refinement algorithm to guarantee the validity of the resulting mesh. If time allows, we will discuss possible extensions to arbitrary metric fields–and not just those deriving from a Hessian.
