×

Generating well-shaped \(d\)-dimensional Delaunay meshes. (English) Zbl 1044.68153

Summary: A \(d\)-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped \(d\)-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a refinement-based method that generates well-shaped \(d\)-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(\(n\)) \(d\)-simplices, where \(n\) is the smallest number of \(d\)-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Bern, P. Chew, D. Eppstein, J. Ruppert, Dihedral bounds for mesh generation in high dimensions, in: Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, ACM, 1995, pp. 189-196.; M. Bern, P. Chew, D. Eppstein, J. Ruppert, Dihedral bounds for mesh generation in high dimensions, in: Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, ACM, 1995, pp. 189-196. · Zbl 0849.68116
[2] Cavendish, J. C.; Field, D. A.; Frey, W. H., An approach to automatic three-dimensional finite element mesh generation, Internat. J. Numer. Methods Eng., 21, 329-347 (1985) · Zbl 0573.65090
[3] S.W. Cheng, T.K. Dey, H. Edelsbrunner, M.A. Facello, S.H. Teng, Silver exudation, in: Proc. 15th ACM Symp. on Computational Geometry, 1999, pp. 1-13.; S.W. Cheng, T.K. Dey, H. Edelsbrunner, M.A. Facello, S.H. Teng, Silver exudation, in: Proc. 15th ACM Symp. on Computational Geometry, 1999, pp. 1-13.
[4] Chew, L. P., Constrained Delaunay triangulations, Algorithmica, 4, 97-108 (1989) · Zbl 0664.68042
[5] L.P. Chew, Guaranteed-quality delaunay meshing in 3d (short version), in: 13th ACM Symp. on Computational Geometry, 1997, pp. 391-393.; L.P. Chew, Guaranteed-quality delaunay meshing in 3d (short version), in: 13th ACM Symp. on Computational Geometry, 1997, pp. 391-393.
[6] H. Edelsbrunner, X.Y. Li, G. Miller, A. Stathopoulos, D. Talmor, S.H. Teng, A. ÜNgÖR”, N. Walkington, Smoothing and cleaning up slivers, in: ACM Symp. on Theory of Computing (STOC00), 2000, pp. 273-277.; H. Edelsbrunner, X.Y. Li, G. Miller, A. Stathopoulos, D. Talmor, S.H. Teng, A. ÜNgÖR”, N. Walkington, Smoothing and cleaning up slivers, in: ACM Symp. on Theory of Computing (STOC00), 2000, pp. 273-277. · Zbl 1296.68175
[7] Edelsbrunner, H.; Shah, N. R., Incremental topological flipping works for regular triangulations, Algorithmica, 15, 223-241 (1996) · Zbl 0840.68050
[8] X.Y. Li, Sliver-free three dimensional delaunay mesh generation, Ph.D. Thesis, University of Illinois at Urbana-Champaign, 2000.; X.Y. Li, Sliver-free three dimensional delaunay mesh generation, Ph.D. Thesis, University of Illinois at Urbana-Champaign, 2000.
[9] X.Y. Li, S.H. Teng, Sliver-free three dimensional delaunay mesh generation, in: Symp. on Discrete Algorithms (SODA), 2001, pp. 28-37.; X.Y. Li, S.H. Teng, Sliver-free three dimensional delaunay mesh generation, in: Symp. on Discrete Algorithms (SODA), 2001, pp. 28-37.
[10] G.L. Miller, D. Talmor, S.H. Teng, N. Walkington, A delaunay based numerical method for three dimensions: generation, formulation, and partition, in: Proc. 27th Annu. ACM Symp. on Theory and Computing 1995, pp. 683-692.; G.L. Miller, D. Talmor, S.H. Teng, N. Walkington, A delaunay based numerical method for three dimensions: generation, formulation, and partition, in: Proc. 27th Annu. ACM Symp. on Theory and Computing 1995, pp. 683-692. · Zbl 0978.68575
[11] J. Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation, in: Third Annu. ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 83-92.; J. Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation, in: Third Annu. ACM-SIAM Symp. on Discrete Algorithms, 1992, pp. 83-92. · Zbl 0801.68163
[12] J.R. Shewchuk, Delaunay refinement mesh generation, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1997.; J.R. Shewchuk, Delaunay refinement mesh generation, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1997. · Zbl 1016.68139
[13] J.R. Shewchuk, Tetrahedral mesh generation by delaunay refinement, in: 14th Ann. ACM Symp. on Computational Geometry, 1998, pp. 86-95.; J.R. Shewchuk, Tetrahedral mesh generation by delaunay refinement, in: 14th Ann. ACM Symp. on Computational Geometry, 1998, pp. 86-95.
[14] D. Talmor, Well-spaced points for numerical methods, Ph.D. Thesis, Carnegie Mellon University, 1997.; D. Talmor, Well-spaced points for numerical methods, Ph.D. Thesis, Carnegie Mellon University, 1997.
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.