Biting: Advancing Front Meets Sphere Packing

XiangYang Li, ShangHua Teng and Alper Üngör

International Journal of Numerical Methods in Engineering (IJNME), (49), 61-81, 2000

Also, presented at 2nd Symposium on Trends in Unstructured Mesh Generation, Boulder, Colorado, August 4-6, 1999

Abstract:

A key step in the finite element method is to generate a high quality mesh that is as small as possible for an input domain. Several meshing methods and heuristics have been developed and implemented. Methods based on advancing front, Delaunay triangulations, and quadtrees/octrees are among the most popular ones. Advancing front uses simple data structures and is efficient. Unfortunately, in general, ot does not provide any guarantee on the size and quality of the mesh it produces. On the other hand, the circle-packing based Delaunay methods generate well-shaped meshes whose size is within a constant factor of the optimal. In this paper, we present a new meshing algorithm, the biting method , which combines the strengths of advancing front and circle packing. We prove that it generates a high quality 2D mesh, and the size of the mesh is within a constant factor of the optimal.