×

zbMATH — the first resource for mathematics

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
Software:
DistMesh; Voronoi; Qhull; CGAL
PDF BibTeX Cite
Full Text: DOI
References:
[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.
[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.
[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)
[6] Liseikin, V.D., Grid generation methods, (1999), 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.
[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.
[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 Lp-norm, Math. comput., 76, 179-204, (2007)
[33] Edelsbrunner, H., Triangulations and meshes in computational geometry, Acta numer., 1-81, (2000)
[34] Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (), 23-90
[35] Fortune, S., Voronoi diagrams and Delaunay triangulations, () · 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.
[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 Rd, in: Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991, pp. 357-363.
[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.
[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, (), 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, (), 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.
[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>. · 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.
[59] 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.