Optimal Voronoi Tessellations with Hessian-based Anisotropy

摘要

This paper presents a variational method to generate cell complexesrnwith local anisotropy conforming to the Hessian of any given convexrnfunction and for any given local mesh density. Our formulationrnbuilds upon approximation theory to offer an anisotropic extensionrnof Centroidal Voronoi Tessellations which can be seen as arndual form of Optimal Delaunay Triangulation. We thus refer to thernresulting anisotropic polytopal meshes as Optimal Voronoi Tessellations.rnOur approach sharply contrasts with previous anisotropicrnversions of Voronoi diagrams as it employs first-type Bregman diagrams,rna generalization of power diagrams where sites are augmentedrnwith not only a scalar-valued weight but also a vectorvaluedrnshift. As such, our OVT meshes contain only convex cellsrnwith straight edges, and admit an embedded dual triangulation thatrnis combinatorially-regular. We show the effectiveness of our techniquernusing off-the-shelf computational geometry libraries.