Parallel delaunay refinement and space-time meshing
Shang‐Hua Teng, Jeff Erickson, Alper Üngör · 2002
We consider the design and analysis of geometric algorithms to partition domains into small, simple and good quality elements suitable for use in numerical simulations. Three problems in this regard are studied in this thesis. The first problem, which was open since the early 1990s, is the parallelization of a set of popular mesh generation algorithms. The second is to formulate and solve a new space-time meshing problem motivated by a recent breakthrough in discontinuous Galerkin finite element methods. The third is to find tilings of three-dimensional domains with acute tetrahedra. Delaunay refinement is a provably good meshing strategy that also performs well in practice. Delaunay refinement algorithms maintain a Delaunay triangulation of a set of points and iteratively add points to generate quality-guaranteed, size-optimal meshes. We parallelize these algorithms and analyze their complexity. We show that the depth of the parallel refinement hierarchy is polylogarithmic in the ratio of the diameter of the domain to its smallest feature. This leads us to claim the first polylogarithmic-time parallel Delaunay refinement algorithms. We also prove that our parallel algorithms provide the same element quality and mesh size guarantees as their sequential counterparts in both two and three dimensions. Space-time finite element methods provide a solution for a wide variety of physical simulation problems. An efficient implementation of these methods requires a special space-time mesh, which allows an independent solution ordering among its elements. We formalize this new meshing problem and describe algorithms to generate simplicial meshes of space-time domains, in constant time per element. We also give an upper bound on the size of the meshes. A tetrahedron is acute if all its dihedral angles are less than 90°. Triangulations of three-dimensional domains with acute tetrahedra are useful in mesh generation. We give several constructions for tiling space with acute tetrahedra.