×

Mesh generation for FEM based on centroidal Voronoi tessellations. (English) Zbl 07312556

Summary: Centroidal Voronoi tessellations (CVTs) are very useful in a variety of applications, which can be used in triangular or tetrahedral mesh generations. There are several algorithms for determining CVTs, including MacQueen’s method, Lloyd’s method, and generalized probabilistic Lloyd’s method. The latter is a combination of MacQueen’s method and Lloyd’s method, which is thought to be one of the most efficient methods to determine high-quality CVTs without the need to explicitly construct Voronoi diagrams. However, the convergence of these methods is difficult to achieve, since they are inclined to be trapped at local minima of cost functional. In this paper, simulated annealing (SA) is introduced to overcome this problem, which is applied to make mesh generation in domains including convex domains, a concaved domain, a multi-connected domain, and a circular domain. The efficiency of this method, and 2-D and 3-D mesh generations are successfully verified through examples.

MSC:

65-XX Numerical analysis
68-XX Computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, T. J., Shape reconstruction and volume meshing for complex solids, Int. J. Numer. Method Eng., 32, 665-675 (1991) · Zbl 0755.76073
[2] Cerny, V., Thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 41-51 (1985) · Zbl 0534.90091
[3] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021
[4] Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133, 591-607 (2002) · Zbl 1024.65118
[5] Du, Q.; Gunzburger, M.; Ju, L., Meshfree, probabilistic determination of point sets and support regions for meshless computing, Comput. Method Appl. Mech. Eng., 191, 1349-1366 (2002) · Zbl 0993.65009
[6] Du, Q.; Gunzburger, M.; Ju, L., Constrained centroidal Voronoi tessellations for surfaces, SIAM J. Sci. Comput., 24, 5, 1488-1506 (2003) · Zbl 1036.65101
[7] Du, Q.; Wang, D. S., Recent progress in robust and quality Delaunay mesh generation, J. Comput. Appl. Math., 195, 8-23 (2006) · Zbl 1096.65016
[8] Du, Q.; Wong, T. W., Numerical studies of MacQueen’s k-means algorithm for computing the centroidal Voronoi tessellations, Comput. Math. Appl., 44, 511-523 (2002) · Zbl 1055.65032
[9] Gosselin, S.; Ollivier-Gooch, C., Tetrahedral mesh generation using Delaunay refinement with non-standard quality measures, Int. J. Numer. Meth. Eng., 87, 795-820 (2011) · Zbl 1242.65257
[10] Goudos, S. K.; Zaharis, Z. D.; Lazaridis, P. I.; Gallion, P. B., Optimization of integrated circuits placement for electric field reduction inside telecommunications equipment using Monte Carlo simulation and parallel recombinative simulated annealing, Microw. Opt. Technol. Lett., 49, 12, 3049-3055 (2007)
[11] Güngör, Z.; Ünler, A., K-harmonic means data clustering with simulated annealing heuristic, Appl. Math. Comput., 184, 199-209 (2007) · Zbl 1114.65009
[12] Ito, Y.; Shih, A. M.; Erukala, A. K.; Soni, B. K.; Chernikov, A.; Chrisochoides, N. P.; Nakahashi, K., Parallel unstructured mesh generation by an advancing front method, Math. Comput. Simul., 75, 200-209 (2007) · Zbl 1124.65025
[13] Ito, Y.; Shih, A. M.; Soni, B., Three-dimensional automatic local remeshing for two or more hybrid meshes, Int. J. Numer. Methods Fluids, 66, 1495-1505 (2011) · Zbl 1220.65025
[14] Ji, S.; Ford, J. C.; Greenwald, R. M.; Beckwith, J. G.; Paulsen, K. D.; Flashman, L. A.; McAllister, T. W., Automated subject-specific, hexahedral mesh generation via image registration, Finite Elem. Anal. Des., 47, 1178-1185 (2011)
[15] Jie, Y. X.; Liu, Y., Simulated annealing based algorithm for node generation in seepage analysis with meshless method, Mech. Res. Commun., 43, 96-100 (2012)
[16] Ju, L.; Du, Q.; Gunzburger, M., Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations, Parallel Comput., 28, 1477-1500 (2002) · Zbl 1014.68202
[17] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[18] Liu, Y.; Xing, H. L.; Guan, Z. Q., An indirect approach for automatic generation of quadrilateral meshes with arbitrary line constraints, Int. J. Numer. Meth. Eng., 87, 906-922 (2011) · Zbl 1242.74137
[19] Locatelli, M., Convergence of a simulated annealing algorithm for continuous global optimization, J. Global Opt., 18, 219-234 (2000) · Zbl 1039.90100
[20] Lohner, R.; Parikh, P., Generation of three-dimensional unstructured grids by the advancing front method, Int. J. Numer. Methods Fluids, 8, 1135-1149 (1988) · Zbl 0668.76035
[21] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H., Equation of state calculations by fast computer machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[22] Taheri, J.; Zomaya, A. Y., A simulated annealing approach for mobile location management, Comput. Commun., 30, 4, 714-730 (2007)
[23] Weatherill, N. P.; Hassan, O., Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints, Int. J. Numer. Method Eng., 37, 2005-2039 (1994) · Zbl 0806.76073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.