Quality mesh generation in three dimensions

ABSTRACT

We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses. First, our triangulation achieves the best possible aspect ratio up to a constant. Second, for any other triangulation of the same region into m triangles with bounded aspect ratio, our triangulation has size n = O(m). Such a triangulation is desired as an initial mesh for a finite element mesh refinement algorithm. Previous three dimensional triangulation schemes either worked only on a restricted class of input, or did not guarantee well-shaped tetrahedra, or were not able to bound the output size. We build on some of the ideas presented in previous work by Bern, Eppstein, and Gilbert, who have shown how to triangulate a two dimensional polyhedral region with holes, with similar quality and optimality bounds.

REFERENCES

• 1: I. Babu~ka and A. K. Aziz {1976}, On the angle condition in the finite element method, SIAM J. Num. Anal. 13:214-226.
• 2: M. Bern, D. Dobkin, and D. Eppstein {1991}, Triangulating polygons without large angles, preprint.
• 3: M. Bern, H. Edelsbrunncr, D. Eppstein, S. Mitchell, and T. S. Tan {1991}, Edge-insertion for optimal triangulations, preprint.
• 4: M. Bern, D. Eppstein, J. Gilbert {1990} Provably Good Mesh Generation, Xerox Palo Alto Research Center. Also, Proc. 1990 Symposium on Foundations of Computer Science.
• 5: M. Bern and D. Eppstein {1991}, Mesh Generation and Optimal Triangulation, preprint.
• 6: G. Carey, M. Sharna, and K. Wang {1988}, A Class of Data Structures for 2-D and 3-D adaptive mesh refinement, Int. Y. Numer. Meth. in Engr. 26:2607- 2622.
• 7: B. Chazelle , L. Palios, Triangulating a non-convex polytype, Proceedings of the fifth annual symposium on Computational geometry, p.393-400, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73876]
• 8: L. P. Chew {1989a}, Constrained Delaunay Triangulation, Algorithmica 4:97-108.
• 9: L. P. Chew {1989b}, Guaranteed-Quality Triangular Meshes, C. S. Cornell, TR 89-983.
• 10: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 11: J. Hauser and C. Taylor {1986}, Numerical Grid Generation in Compuiational Fluid Dynamics (Proceedings), Pineridge Press, Swansea, U.K.
• 12: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 13: G. L. Miller , W. Thurston, Separators in two and three dimensions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.300-309, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100255]
• 14: Gary L. Miller , Stephen A. Vavasis, Density graphs and separators, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.331-336, January 28-30, 1991, San Francisco, California, United States
• 15: W. F. Mitchell {1987}, A Comparison of Adaptive Refinement Techniques for E1}{iptic Problems, Department of Computer Science, University of illinois at Urbana-Champaign, Report No. UIUCDCS-R-87-1375.
• 16: W. F. Mitchell {1988}, Unified Multilevel Adaptive Finite Element Methods for Elliptic Problems, Department of Computer Science, University of Illinois at Urbana-Champaign, Report No. UIUCDCS-R-88-1446.
• 17: D. Moore, J. Warren {1990}, Multidimensional Adaptive Mesh Generation, Department of Computer Science, Rice University, Rice COMP TR 90-106.
• 18: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

General Terms:
Algorithms, Theory