PROVABLY GOOD MESH GENERATION

We study several versions of the problem of generating triangular mesh es for finite element methods. We show how to triangulate a planar poi nt set or 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 w ith simplices of bounded aspect ratio; and how to produce a linear-siz e Delaunay triangulation of a multi-dimensional point set by adding a linear number of extra points. All our triangulations have size (numbe r of triangles) 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 pre vious work on mesh generation simultaneously guarantees well-shaped el ements and small total size. (C) 1994 Academic Press, Inc.