An accelerated scheme with high quality mesh based on Lloyd iteration

Abstract

High quality mesh plays an important role for finite element methods in science computation and numerical simulation. Whether the mesh quality is good or not, to some extent, it determines the calculation results of the accuracy and efficiency. Different from classic Lloyd iteration algorithm which is convergent slowly, a novel accelerated scheme was presented, which consists of two core parts: mesh points replacement and local edges Delaunay swapping. By using it, almost all the equilateral triangular meshes can be generated based on centroidal Voronoi tessellation (CVT). Numerical tests show that it is significantly effective with time consuming decreasing by 40%. Compared with other two types of regular mesh generation methods, CVT mesh demonstrates that higher geometric average quality increases over 0.99.

Keywords

Lloyd iteration / mesh generation / Delaunay triangulation / high quality mesh / centroidal Voronoi tessellation

References

[1] ChenC.-m., HuangY.-Qing.High accuracy theory of finite element methods [M], 1995ChangshaHunan Science and Technology Press299-309

[2] HuangY.-q., QinH.-f., WangD.-sheng.. Centroidal Voronoi tessellation-based finite element superconvergence [J]. International Journal for Numerical Methods in Engineering, 2008, 76: 1819-1839

[3] YanN.-ning.Superconvergence analysis and a posteriori error estimation in finite element methods [M], 2008BeijingScience Press31-35

[4] HuangY.-q., YiN.-yu.. the superconvergence cluster recovery method [J]. Journal of Scientific Computing, 2010, 44(3): 301-322

[5] GEORGE P L. Mesh generation: Application to finite element [M]. ISTE Ltd and John Wiley & Sons, Inc., 2008: 201–231.

[6] TaoW.-quan.The new progresses on numerical heat transfer [M], 2000BeijingScience Press19-104

[7] HuangY.-q., QinH.-f., et al. . Convergent adaptive finite element method based on centroidal Voronoi tessellations and superconvergence [J]. Communications in Computational Physics, 2011, 10(2): 339-370

[8] DuQ., WangD.-sheng.. Anisotropic centroidal Voronoi tessellations and their applications [J]. SIAM J Sci Comput, 2005, 26(3): 737-761

[9] DuQ., EmeliaenkoM., JuL.-li.. Convergence of the Lloyd Algorithm for computing centroidal Voronoi tessellations [J]. SIAM J Numer Anal, 2006, 44(1): 102-119

[10] JuL.-li.. Conforming centroidal Voronoi Delaunay triangulation for quality mesh generation [J]. International Journal of Numerical Analysis and Modeling, 2007, 4(3): 531-547

[11] DuQ., WangD.-sheng.. Tetrahedral mesh generation and optimization based on Centroidal Voronoi Tessellations [J]. International Journal for Numerical Methods in Engineering, 2003, 56(2): 1355-1373

[12] LloydS.. Least square quantization in PCM [J]. IEEE Trans Infor Theory, 1982, 28: 129-137

[13] DuQ., EmelianenkoM.. Acceleration schemes for computing centroidal Voronoi tessellations [J]. Numer Linear Algebra Appl, 2006, 13: 173-192

[14] LiuY., WangW.-p., LevyB., et al. . On centroidal voronoi tessellation-Energy smoothness and fast computation [J]. ACM Transactions on Graphics, 2009, 28(4): 1-32

[15] DuQ., GunzburgerM.. Grid generation and optimization based on Centroidal Voronoi Tessellations [J]. Applied and Computational Mathematics, 2002, 133: 591-607