Geodesic
Boundary conforming Delaunay mesh generation
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 1, pp. 44-59 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. It's 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 $\arccos1/3\approx 70.53^\circ$. In addition, well-shaped tetrahedra and 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. 
@article{ZVMMF_2010_50_1_a5,
     author = {K. G\"artner and H. Si and J. Fuhrmann},
     title = {Boundary conforming {Delaunay} mesh generation},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {44--59},
     year = {2010},
     volume = {50},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_1_a5/}
}
TY  - JOUR
AU  - K. Gärtner
AU  - H. Si
AU  - J. Fuhrmann
TI  - Boundary conforming Delaunay mesh generation
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 44
EP  - 59
VL  - 50
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_1_a5/
LA  - en
ID  - ZVMMF_2010_50_1_a5
ER  - 
%0 Journal Article
%A K. Gärtner
%A H. Si
%A J. Fuhrmann
%T Boundary conforming Delaunay mesh generation
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 44-59
%V 50
%N 1
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_1_a5/
%G en
%F ZVMMF_2010_50_1_a5
K. Gärtner; H. Si; J. Fuhrmann. Boundary conforming Delaunay mesh generation. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 1, pp. 44-59. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_1_a5/

[1] Macneal R. H., “An asymmetrical finite difference network”, Quart. Math. Appl., 11 (1953), 295–310 | MR | Zbl

[2] Voronoi G., “Nouvelles applications des parameters continues a la theorie de formas quadratiques”, Reine Angew. Math., 133 (1907), 97–178

[3] Alen D., Southwell R., “Relaxation methods applied to determine the motion, in two dimensions, of a viscous fluid past a fixed cylinder”, Quart. J. Mech. and Appl. Math., 8 (1955), 129–145 | DOI | MR

[4] Il'in A. M., “A difference scheme for a differential equation with a small parameter multiplying the second derivative”, Mat. Zametki, 6:2 (1969), 237–248 | MR

[5] Scharfetter D. L., Gummel H. K., “Large signal analysis of a silicon Read diode”, IEEE Trans. Electron. Dev., 16 (1969), 64–77 | DOI

[6] Eymard R., Fuhrmann J., Gärtner K., “A finite volume scheme for nonlinear parabolic equations derived from one-dimensional local Dirichlet problems”, Numer. Math., 102:3 (2006), 463–495 | DOI | MR | Zbl

[7] Varga R. S., Matrix iterative analysis, Prentice-Hall, 1962 | MR

[8] Eymard R., Gallouët T., Herbin R., “The finite volume method”, Handbook Numer. Analys., 7, North-Holland, 2000, 715–1022 | MR

[9] Fuhrmann J., Langmach H., “Stability and existence of solutions of time-implicit finite volume schemes for viscous nonlinear conservation laws”, Appl. Numer. Math., 37:1–2 (2001), 201–230 | DOI | MR | Zbl

[10] Gajewski H., Gärtner K., “On the discretization of van Roosbroeck's equations with magnetic field”, Z. angew. Math. und Mech., 76:5 (1996), 247–264 | DOI | MR | Zbl

[11] Gärtner K., “Existence of bounded discrete steady state solutions of the van Roosbroeck system on boundary conforming Delaunay grids”, SIAM J. Sci. Comput., 31 (2009), 1347–1362 | DOI | MR

[12] Glitzky A., Gärtner K., Energy estimates for continuous and discretized electro-reaction-diffusion systems, Preprint 1222. Techn. Rep. WIAS, 2007 | MR | Zbl

[13] Linke A., Divergence-free mixed finite elements for the incompressible Navier–Stokes equation, PhD thesis, Univ. Erlangen, 2008

[14] Delaunay B. N., “Sur la sphere vide”, Izvestia Adakemii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 1934, no. 6, 793–800 | Zbl

[15] Gabriel K. R., Sokal R. R., “A new statistical approach to geographic analysis”, Systematic Zoology, 18:3 (1969), 259–278 | DOI

[16] Chew P. L., Guaranteed-quality triangular meshes, Techn. Rept. TR 89-983, Dept. Comput. Sci. Cornell Univ., 1989

[17] Ruppert J., “A Delaunay refinement algorithm for quality 2-dimensional mesh generation”, J. Algorithms, 18:3 (1995), 548–585 | DOI | MR | Zbl

[18] Shewchuk J. R., “Tetrahedral mesh generation by Delaunay refinement”, Proc. 14th Ann. Symp. Comput. Geom., 1998, 86–95

[19] Si H., Three dimensional boundary conforming Delaunay mesh generation, PhD thesis, Inst. Math., Techn. Univ., Berlin, 2008

[20] Si H., “An analysis of Shewchuk's Delaunay refinement algorithm”, Proc. 18th Intern. Mesh. Rountable, 2009

[21] Cheng S.-W., Dey T., Edelsbrunner H., et al., “Sliver exudation”, J. Assoc. Comput. Mack., 47 (2000), 883–904 | MR

[22] Erickson J., “Nice point sets can have nasty Delaunay triangulations”, Discreta Comput. Geometry, 30:1 (2003), 109–132 | DOI | MR | Zbl

[23] Si H., Gärtner K., “Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations”, Proc. 14th Internat. Mesh. Roundtable, 2005, 147–163

[24] Li X.-Y., Teng S.-H., “Generating well-shaped Delaunay meshes in 3D”, Proc. 12th Ann. ACM-SIAM Symp. on Disc. Algo, 2001, 28–37 | MR | Zbl

[25] Si H., , 2009, Last retrieved 2009-10-27 http://tetgen.berlios.de

[26] Si H., “Adaptive tetrahedral mesh generation by constrained Delaunay refinement”, Inter. J. Numer. Meth. Engin., 75:7 (2008), 856–880 | DOI | MR | Zbl

[27] Cheng S.-W., Dey T. K., Ramos E. A., Ray T., “Quality meshing for polyhedra with small angles”, Inter. J. Comput. Geometry. Appl., 15 (2005), 421–461 | DOI | MR

[28] Pav S. E., Walkington N. J., “Robust three dimensional Delaunay refinement”, Proc. 13th Internat. Mesh. Roundtable, Sandia Nation. Lab., 2004 | Zbl

[29] Pav S. E., Delaunay refinement algorithm, PhD thesis, Carnegie Mellon Univ., 2003 | MR