Provably Good Mesh Generation

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. >

Authors

• Marshall W. Bern
• David Eppstein
• John R. Gilbert

Keywords

• Mesh generation
• Finite element methods
• Polynomials
• Solid modeling
• Design automation
• Rendering (computer graphics)
• Tree graphs
• Geometry
• Data analysis
• Computer science
• Aspect Ratio
• Finite Element Method
• Constant Factor
• Points In Plane
• Obtuse Angle
• N Log N
• Diagonal
• Crowding
• Mesh Size
• Small Angle
• Line Segment
• Balanced State
• Clusters Of Points
• Minimum Angle
• Input Point
• Geodesic Distance
• Internal Angle
• Number Of Boxes
• Segmentation Points
• Side Of The Box
• Corner Of The Box
• Empty Box
• Delaunay Triangulation
• Right Triangle
• Isosceles Triangle
• Partitioning Problem
• Simple Heuristics
• Minimum Bounding