Provably good mesh generation
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 231-241
- https://doi.org/10.1109/fscs.1990.89542
Abstract
Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size.<>Keywords
This publication has 13 references indexed in Scilit:
- Separators in two and three dimensionsPublished by Association for Computing Machinery (ACM) ,1990
- Guaranteed-Quality Triangular MeshesPublished by Defense Technical Information Center (DTIC) ,1989
- The design and application of upwind schemes on unstructured meshesPublished by American Institute of Aeronautics and Astronautics (AIAA) ,1989
- Triangulating a non-convex polytypePublished by Association for Computing Machinery (ACM) ,1989
- Approaches to the Automatic Generation and Control of Finite Element MeshesApplied Mechanics Reviews, 1988
- Constrained Delaunay triangulationsPublished by Association for Computing Machinery (ACM) ,1987
- Generalized delaunay triangulation for planar graphsDiscrete & Computational Geometry, 1986
- Generalized Nested DissectionSIAM Journal on Numerical Analysis, 1979
- Locally equiangular triangulationsThe Computer Journal, 1978
- Condition of finite element matrices generated from nonuniform meshes.AIAA Journal, 1972