Efficient mesh optimization schemes based on optimal Delaunay triangulations. (English) Zbl 1225.65113
Summary: In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted \(L^{1}\) norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.
MSC:
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
Keywords:
mesh smoothing; mesh optimization; mesh generation; Delaunay triangulation; optimal Delaunay triangulationReferences:
| [1] | L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, in: 13th International Meshing Roundtable, Sandia National Laboratories, Williamsburg, VA, 2004, pp. 109-120.; L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, in: 13th International Meshing Roundtable, Sandia National Laboratories, Williamsburg, VA, 2004, pp. 109-120. |
| [2] | Chen, L.; Xu, J., Optimal Delaunay triangulations, J. Comput. Math., 22, 299-308 (2004) · Zbl 1048.65020 |
| [3] | L. Chen, Robust and accurate algorithms for solving anisotropic singularities, Ph.D. thesis, Department of Mathematics, The Pennsylvania State University, 2005.; L. Chen, Robust and accurate algorithms for solving anisotropic singularities, Ph.D. thesis, Department of Mathematics, The Pennsylvania State University, 2005. |
| [4] | Knupp, P.; Steinberg, S., Fundamentals of Grid Generation (1994), CRC Press · Zbl 0855.65123 |
| [5] | Carey, G., Computational Grids: Generation, Adaptation, and Solution Strategies, CRC (1997) · Zbl 0955.74001 |
| [6] | Liseikin, V. D., Grid Generation Methods (1999), Springer Verlag: Springer Verlag Berlin · Zbl 0949.65098 |
| [7] | Huang, W., Variational mesh adaptation: isotropy and equidistribution, J. Comput. Phys., 174, 903-924 (2001) · Zbl 0991.65131 |
| [8] | Dvinsky, A. S., Adaptive grid generation from harmonic maps on Riemannian manifolds, J. Comput. Phys., 95, 450-476 (1991) · Zbl 0733.65074 |
| [9] | Huang, W.; Russell, R. D., Moving mesh strategy based on a gradient flow equation for two-dimensional problems, SIAM J. Sci. Comput., 20, 998-1015 (1999) · Zbl 0956.76076 |
| [10] | Li, R.; Tang, T.; Zhang, P., Moving mesh methods in multiple dimensions based on harmonic maps, J. Comput. Phys., 170, 562-588 (2001) · Zbl 0986.65090 |
| [11] | Anderson, A.; Zheng, X.; Cristini, V., Adaptive unstructured volume remeshing – i: the method, J. Comput. Phys., 208, 616-625 (2005) · Zbl 1075.65119 |
| [12] | Persson, P.-O.; Strang, G., A simple mesh generator in matlab, SIAM Rev., 46, 329-345 (2004) · Zbl 1061.65134 |
| [13] | Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133, 591-607 (2002) · Zbl 1024.65118 |
| [14] | Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021 |
| [15] | Brown, K. Q., Voronoi diagrams from convex hulls, Inform. Process. Lett., 9, 223-228 (1979) · Zbl 0424.68036 |
| [16] | Barber, C.; Dobkin, D.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM Trans. Math. Softw. (TOMS), 22, 469-483 (1996) · Zbl 0884.65145 |
| [17] | Aiffa, M.; Flaherty, J. E., A geometrical approach to mesh smoothing, Comput. Meth. Appl. Mech. Engrg., 192, 4497-4514 (2003) · Zbl 1040.65102 |
| [18] | Amenta, N.; Bern, M.; Eppstein, D., Optimal point placement for mesh smoothing, J. Algorithms, 302-322 (1999) · Zbl 0919.65070 |
| [19] | Bank, R. E.; Smith, R. K., Mesh smoothing using a posteriori error estimates, SIAM J. Numer. Anal., 34, 979-997 (1997) · Zbl 0873.65092 |
| [20] | Freitag, L. A.; Jones, M. T.; Plassmann, P. E., A parallel algorithm for mesh smoothing, SIAM J. Sci. Comput., 20, 2023-2040 (1999) · Zbl 0939.65132 |
| [21] | Freitag, L.; Ollivier-Gooch, C., Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Meth. Engrg., 40, 3979-4002 (1997) · Zbl 0897.65075 |
| [22] | Freitag, L., On combining Laplacian and optimization-based mesh smoothing techniques. AMD trends in unstructured mesh generation, ASME, 220, July, 37-43 (1997) |
| [23] | T. Zhou, K. Shimada, An angle-based approach to two-dimensional mesh smoothing, in: 9th International Meshing Roundtable, Sandia National Laboratories, 2000, pp. 373-384.; T. Zhou, K. Shimada, An angle-based approach to two-dimensional mesh smoothing, in: 9th International Meshing Roundtable, Sandia National Laboratories, 2000, pp. 373-384. |
| [24] | Alliez, P.; Cohen-Steiner, D.; Yvinec, M.; Desbrun, M., Variational tetrahedral meshing, ACM Trans. Graph., 24, 617-625 (2005) |
| [25] | M. Berndt, M. Shashkov, Multilevel accelerated optimization for problems in grid generation, in: Proceedings of the 12th International Meshing Roundtable, Sandia Nat. Lab., 2003, pp. 351-359.; M. Berndt, M. Shashkov, Multilevel accelerated optimization for problems in grid generation, in: Proceedings of the 12th International Meshing Roundtable, Sandia Nat. Lab., 2003, pp. 351-359. |
| [26] | Koren, Y.; Yavneh, I.; Spira, A., A multigrid approach to the scalar quantization problem, IEEE Trans. Inform. Theory, 51, 2993-2998 (2005) · Zbl 1297.94028 |
| [27] | Koren, Y.; Yavneh, I., Adaptive multiscale redistribution for vector quantization, SIAM J. Sci. Comput., 27, 1573-1593 (2006) · Zbl 1100.68120 |
| [28] | Spitaleri, R. M., Full-fas multigrid grid generation algorithms, Appl. Numer. Math., 32, 483-494 (2000) · Zbl 0973.65114 |
| [29] | Du, Q.; Emelianenko, M., Uniform convergence of a nonlinear energy-based multilevel quantization scheme, SIAM J. Numer. Anal., 46, 1483-1502 (2008) · Zbl 1171.65011 |
| [30] | Chen, L., New analysis of the sphere covering problems and optimal polytope approximation of convex bodies, J. Approx. Theory, 133, 134-145 (2005) · Zbl 1072.65021 |
| [31] | Chen, L., On minimizing the linear interpolation error of convex quadratic functions, East J. Approx., 14, 271-284 (2008) · Zbl 1217.41009 |
| [32] | Chen, L.; Sun, P.; Xu, J., Optimal anisotropic simplicial meshes for minimizing interpolation errors in \(L^p\)-norm, Math. Comput., 76, 179-204 (2007) · Zbl 1106.41013 |
| [33] | Edelsbrunner, H., Triangulations and meshes in computational geometry, Acta Numer., 1-81 (2000) |
| [34] | Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (Du, D.-Z.; Hwang, F., Computing in Euclidean Geometry. Computing in Euclidean Geometry, Lecture Notes Series on Computing, vol. 1 (1992), World Scientific), 23-90 · Zbl 0811.68054 |
| [35] | Fortune, S., Voronoi diagrams and Delaunay triangulations, (Du, Ding-Zhu; Hwang, Frank, Computing in Euclidean Geometry. Computing in Euclidean Geometry, Lecture Notes Series on Computing, vol. 1 (1992), World Scientific) · Zbl 0907.68190 |
| [36] | Sibson, R., Locally equiangular triangulations, Comput. J., 21, 243-245 (1978) |
| [37] | T. Lambert, The Delaunay triangulation maximize the mean inradius, in: Proceedings of the 6th Canadian Conference on Computational Geometry, 1994, pp. 201-206.; T. Lambert, The Delaunay triangulation maximize the mean inradius, in: Proceedings of the 6th Canadian Conference on Computational Geometry, 1994, pp. 201-206. |
| [38] | Rippa, S., Minimal roughness property of the Delaunay triangulation, Comput. Aided Geom. Des., 7, 489-497 (1990) · Zbl 0714.65009 |
| [39] | D’Azevedo, E. F.; Simpson, R. B., On optimal interpolation triangle incidences, SIAM J. Sci. Statist. Comput., 6, 1063-1075 (1989) · Zbl 0705.41001 |
| [40] | V.T. Rajan, Optimality of the Delaunay triangulation in \(R^d\); V.T. Rajan, Optimality of the Delaunay triangulation in \(R^d\) |
| [41] | Rippa, S., Long and thin triangles can be good for linear interpolation, SIAM J. Numer. Anal., 29, 257-270 (1992) · Zbl 0748.65011 |
| [42] | E.A. Melissaratos, Lp Optimal d Dimensional Triangulations for piecewise linear interpolation: a new result on data dependent triangulations, Technical Report RUU-CS-93-13, Department of Information and Computing Sciences, Utrecht University, 1993.; E.A. Melissaratos, Lp Optimal d Dimensional Triangulations for piecewise linear interpolation: a new result on data dependent triangulations, Technical Report RUU-CS-93-13, Department of Information and Computing Sciences, Utrecht University, 1993. |
| [43] | Mitrinovic, D. S.; Pecaric, J. E.; Volenec, V., Recent advances in geometric inequalities, Math. Appl. East Eur. Ser., 28 (1989) · Zbl 0679.51004 |
| [44] | Guibas, L. J.; Knuth, D. E.; Sharir, M., Randomized incremental construction of Delaunay and Voronoi diagrams, (Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming (1990), Springer-Verlag Inc.: Springer-Verlag Inc. New York, NY, USA), 414-431 · Zbl 0765.68207 |
| [45] | Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Disc. Comp. Geom., 8, 25-44 (1986) · Zbl 0598.52013 |
| [46] | Edelsbrunner, H.; Li, X.-Y.; Miller, G.; Stathopoulos, A.; Talmor, D.; Teng, S.-H.; Üngör, A.; Walkington, N., Smoothing and cleaning up slivers, (STOC’00: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (2000), ACM: ACM New York, NY, USA), 273-277 · Zbl 1296.68175 |
| [47] | Xu, H.; Newman, T. S., An angle-based optimization approach for 2d finite element mesh smoothing, Finite Elem. Anal. Des., 42, 1150-1164 (2006) |
| [48] | Parthasarathy, V.; Kodiyalam, S., A constrained optimization approach to finite element mesh smoothing, Finite Elem. Anal. Des., 9, 309-320 (1991) · Zbl 0850.73326 |
| [49] | Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, Int. J. Numer. Meth. Engrg., 56, 1355-1373 (2003) · Zbl 1106.74431 |
| [50] | Du, Q.; Wang, D., Recent progress in robust and quality Delaunay mesh generation, J. Comput. Math., 195, 8-23 (2006) · Zbl 1096.65016 |
| [51] | Du, Q.; Gunzburger, M.; Ju, L., Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere, Comput. Meth. Appl. Mech. Engrg., 192, 3933-3957 (2003) · Zbl 1046.65094 |
| [52] | Ju, L., Conforming centroidal voronoi delaunay triangulation for quality mesh generation, Int. J. Numer. Anal. Model., 4, 531-547 (2007) · Zbl 1132.65012 |
| [53] | Ju, L.; Gunzburger, M.; Zhao, W., Adaptive finite element methods for elliptic PDEs based on conforming centroidal Voronoi Delaunay triangulations, SIAM J. Sci. Comput., 28, 2023-2053 (2007) · Zbl 1126.65099 |
| [54] | Field, D. A., Laplacian smoothing and Delaunay triangulation, Commun. Appl. Numer. Meth., 4, 709-712 (1988) · Zbl 0664.65107 |
| [55] | D.A. Spielman, S.-H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Preliminary Draft, 2006.; D.A. Spielman, S.-H. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Preliminary Draft, 2006. |
| [56] | Xu, J., Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal., 33, 1759-1777 (1996) · Zbl 0860.65119 |
| [57] | CGAL, Computational Geometry Algorithms Library, <http://www.cgal.org>; CGAL, Computational Geometry Algorithms Library, <http://www.cgal.org> · Zbl 1365.68441 |
| [58] | J.R. Shewchuk, Tetrahedral mesh generation by Delaunay refinement, in: 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 86-95.; J.R. Shewchuk, Tetrahedral mesh generation by Delaunay refinement, in: 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 86-95. |
| [59] | T.K. Dey, Delaunay mesh generation of three dimensional domains, Technical Report OSU-CISRC-9/07-TR64, 2007.; T.K. Dey, Delaunay mesh generation of three dimensional domains, Technical Report OSU-CISRC-9/07-TR64, 2007. |
| [60] | Tournois, J.; Wormser, C.; Alliez, P.; Desbrun, M., Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation, ACM Trans. Graph., 28, 1-9 (2009) |
| [61] | Du, Q.; Wang, D., Constrained boundary recovery for three dimensional Delaunay triangulations, Int. J. Numer. Meth. Engrg., 61, 1471-1500 (2004) · Zbl 1073.65511 |
| [62] | Du, Q.; Gunzburger, M.; Ju, L., Constrained centroidal Voronoi tessellations for surfaces, SIAM J. Sci. Comput., 24, 1488-1506 (2003) · Zbl 1036.65101 |
| [63] | Yu, Z.; Holst, M. J.; McCammon, J. A., High-fidelity geometric modeling for biomedical applications, Finite Elem. Anal. Des., 44, 715-723 (2008) |
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.
