×

zbMATH — the first resource for mathematics

Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains. (English) Zbl 1059.65022
Generation and refinement of tetrahedral meshes are considered here. The approach of the authors consists of two steps (i) sequential mesh initialization and (ii) parallel mesh refinement. The significant feature of the authors’ algorithm is that the submesh interface are allowed to change as new vertices are inserted concurrently in to the distributed mesh. The authors prove that the parallel refinement algorithm terminates, and generates a new distributed Delauney mesh containing tetrahedra whose circumradius to shortest edge ratio is less than 2.

MSC:
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y05 Parallel numerical computation
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
Software:
ParMETIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Karypis, G.; Schloegel, K.; Kumar, V., PARMETIS—parallel graph partitioning and sparse matrix ordering library, (1998), University of Minnesota Minneapolis, MN, Version 2.0
[2] Miller, G.L.; Talmor, D.; Teng, S.-H.; Walkington, N.; Wang, H., Control volume meshes using sphere packing: generation, refinement, and coarsening, (), 47-61
[3] Murphy, M.; Mount, D.M.; Gable, C.W., A point placement strategy for conforming Delaunay tetrahedralization, (), 67-74 · Zbl 0953.65010
[4] Cohen-Steiner, D.; de Verdiere, E.C.; Yvinec, M., Conforming Delaunay triangulations in 3d, () · Zbl 1054.65018
[5] Chrisochoides, N.; Nave, D., Parallel Delaunay mesh generation kernel, Internat. J. numer. methods engrg., 58, 2, 161-176, (2003) · Zbl 1035.65018
[6] Löhner, R.; Cebral, J., Parallel advancing front grid generation, (), 67-74
[7] Said, R.; Weatherill, N.; Morgan, K.; Verhoeven, N., Distributed parallel Delaunay mesh generation, Comput. meth. appl. mech. engrg., 177, 109-125, (1999) · Zbl 0997.65137
[8] de Cougny, H.; Shephard, M., Parallel volume meshing using face removals and hierarchical repartitioning, Comput. meth. appl. mech. engrg., 174, 3-4, 275-298, (1999) · Zbl 0963.76073
[9] D. Mavriplis, S. Pirzadeh, Large-scale parallel unstructured mesh computations for 3d high-lift analysis, Tech. Rep. NASA/CR-1999-208999 and ICASE Report No. 99-9, Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, VA, 1999
[10] Oliker, L.; Biswas, R.; Strawn, R.C., Parallel implementation of an adaptive scheme for 3d unstructured grids on the sp2, (), 35-47
[11] H.L. deCougny, K.D. Devine, R.M.L.J.E. Flaherty, C. Ozturan, M.S. Shephard, Load balancing of parallel adaptive solutions of partial differential equations, Tech. Rep. TR94-8, Rensselaer Polytechnic Institute, Department of Computer Science, 1994 · Zbl 0818.65099
[12] Chrisochoides, N.; Sukup, F., Task parallel implementation of the BOWYER-WATSON algorithm, ()
[13] Okusanya, T.; Peraire, J., Parallel unstructured mesh generation, ()
[14] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 2, 162-166, (1981)
[15] Watson, D.F., Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Comput. J., 24, 2, 167-172, (1981)
[16] Okusanya, T.; Peraire, J., 3D parallel unstructured mesh generation, (), 109-116
[17] Bonet, J.; Peraire, J., An alternating digital tree (ADT) algorithm for 3d geometric searching and intersection problems, Internat. J. numer. meth. engrg., 31, 1-17, (1991) · Zbl 0825.73958
[18] Chew, P.; Chrisochoides, N.; Sukup, F., Parallel constrained Delaunay meshing, ()
[19] Shewchuk, J.R., A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, (), 76-85
[20] Galtier, J.; George, P.L., Prepartitioning as a way to mesh subdomains in parallel, ()
[21] Shewchuk, J.R., Tetrahedral mesh generation by Delaunay refinement, (), 86-95
[22] Shewchuk, J.R., Mesh generation for domains with small angles, (), 111-112
[23] Freitag, L.A.; Jones, M.T.; Plassmann, P.E., The scalability of mesh improvement algorithms, (), 185-212 · Zbl 0940.68182
[24] Lawson, C., Software for C1 surface interpolation, (), 161-194
[25] Joe, B., Construction of three-dimensional Delaunay triangulations using local transformations, Computer aided geometric design, 10, 123-142, (1989) · Zbl 0729.65120
[26] Mücke, E.P.; Saias, I.; Zhu, B., Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, (), 274-283
[27] Chew, L.P., Guaranteed-quality Delaunay meshing in 3-D (short version), (), 391-393
[28] Li, X.-Y., Spacing control and sliver-free Delaunay mesh, (), 295-306
[29] Edelsbrunner, H., Geometry and topology for mesh generation, (2001), Cambridge University Press Cambridge, England · Zbl 0981.65028
[30] Cheng, S.-W.; Dey, T.K., Quality meshing with weighted Delaunay refinement, (), 137-146 · Zbl 1058.65022
[31] Chrisochoides, N.; Barker, K.; Nave, D.; Hawblitzel, C., Mobile object layer: A runtime substrate for parallel adaptive and irregular computations, Adv. engrg. software, 31, 8-9, 621-637, (2000) · Zbl 1003.68540
[32] Chrisochoides, N.; Nave, D., Simultaneous mesh generation and partitioning, Mathematics and computers in simulation, 54, 4-5, 321-339, (2000) · Zbl 0993.65029
[33] Luby, M., A simple parallel algorithm for the maximal independent set, SIAM J. comput., 15, 1036-1053, (1986) · Zbl 0619.68058
[34] J.R. Shewchuk, Delaunay refinement mesh generation, PhD Thesis, Carnegie Mellon University, School of Computer Science, available as Technical Report CMU-CS-97-137, May 1997 · Zbl 1016.68139
[35] H. Borouchaki, P.L. George, S.H. Lo, Optimal Delaunay point insertion, Internat. J. Numer. Meth. Engrg. 39 · Zbl 0883.73086
[36] Remacle, J.-F.; Karamete, B.K.; Shephard, M.S., Algorithm oriented mesh database, (), 349-359
[37] Barker, K.; Chrisochoides, N.; Dobbelaere, J.; Nave, D.; Pingali, K., Data movement and control substrate for parallel, adaptive applications, Concurrency and computation practice and experience, 14, 1-15, (2002)
[38] Shewchuk, J.R., Robust adaptive floating-point geometric predicates, (), 141-150
[39] Löhner, R.; Camberos, J.; Marshal, M., Parallel unstructured grid generation, Unstructured scientific computation on scalable multiprocessors, 31-64, (1990)
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.