Premium
Biting: advancing front meets sphere packing
Author(s) -
Li XiangYang,
Teng ShangHua,
Üngör Alper
Publication year - 2000
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/1097-0207(20000910/20)49:1/2<61::aid-nme923>3.0.co;2-y
Subject(s) - delaunay triangulation , heuristics , circle packing , computer science , polygon mesh , mesh generation , domain (mathematical analysis) , constant (computer programming) , mathematical optimization , finite element method , algorithm , simple (philosophy) , topology (electrical circuits) , mathematics , geometry , computer graphics (images) , engineering , combinatorics , structural engineering , mathematical analysis , philosophy , epistemology , programming language
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 circle‐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 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. Copyright © 2000 John Wiley & Sons, Ltd.