Biting: Advancing Front Meets Sphere Packing

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Department of Computer Science, University of Illinois at Urbana- Champaign, Urbana, IL 61801
[xli2 | steng | ungor] @cs.uiuc.edu

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, it does not provide any guarantee on the size and quality of the mesh it produces. On the other hand, the sphere-packing based Delaunay methods generate a well-shaped mesh 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 sphere packing.

In this paper, we show that the advancing front method can be used to efficiently construct a quality sphere-packing. At a high level, this new advancing front based packing algorithm first finds a sphere packing of the boundary of the domain and then grows the packing towards the interior of the domain. Each time when a new sphere is added to the interior, a larger protection sphere is removed (bitten away) from the domain so that no future sphere will overlap with this one. By doing this, it builds the sphere packing by adding spheres one at a time, or a layer at a time, in the same spirit as the standard advancing method; our new method uses advancing front to construct a sphere packing instead of the mesh elements themselves. We show that this advancing front based method does generate a well-spaced point set, whose Delaunay triangulation is well-shaped. We will refer this new method as the biting method and show that it can be made as practical as the standard advancing front meshing methods. Biting sphere at a point x is B(x, c