05884320

j

05884320 G\"artner, K. Si, H. Fuhrmann, J. Boundary conforming Delaunay mesh generation. Zh. Vychisl. Mat. Mat. Fiz. 50, No. 1, 44-59 (2010) and Comput. Math., Math. Phys. 50, No. 1, 38-53 (2010). 2010 Rossi\u{\i}skaya Akademiya Nauk, Moskva; "Nauka", Moskva EN Delaunay mesh Voronoi partition partitions of polyhedra finite volume schemes Delaunay refinement algorithm

doi:10.1134/S0965542510010069

http://www.maik.ru/abstract/commat/10/commat1_10p38abs.htm

Summary: A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay simplices such that all boundary simplices satisfy the generalized Gabriel property. Its dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains, however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by$\arccos 1/3 \approx 70.53^{\circ}$. In addition, well-shaped tetrahedra and an appropriate mesh size can be obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical guarantee on the input angle $70.53^{\circ}$ is still too strong for many practical situations. We further discuss variants of the algorithm to relax the input angle restriction and to improve the mesh quality.