Quality mesh generation in three dimensions

TLDR

A high‑quality initial mesh for finite element refinement requires well‑shaped tetrahedra, but existing 3‑D triangulation schemes are limited or lack size guarantees, motivating a new approach that extends prior 2‑D work. The study aims to provide a method for triangulating a three‑dimensional polyhedral region with holes. The authors present an algorithm that constructs such a triangulation by subdividing the region into tetrahedra while respecting the holes. The resulting triangulation achieves an optimal aspect ratio up to a constant and has size O(m) compared to any other bounded‑aspect‑ratio triangulation of the same region.

Abstract

We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses. First, our triangulation achieves the best possible aspect ratio up to a constant. Second, for any other triangulation of the same region into m triangles with bounded aspect ratio, our triangulation has size n = O(m). Such a triangulation is desired as an initial mesh for a finite element mesh refinement algorithm. Previous three dimensional triangulation schemes either worked only on a restricted class of input, or did not guarantee well-shaped tetrahedra, or were not able to bound the output size. We build on some of the ideas presented in previous work by Bern, Eppstein, and Gilbert, who have shown how to triangulate a two dimensional polyhedral region with holes, with similar quality and optimality bounds.