Generating well-shaped d-dimensional Delaunay Meshes

✍ Scribed by Xiang-Yang Li

• Book ID: 104325529
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 193 KB
• Volume: 296
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00437-1

✦ Synopsis

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a reÿnement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.