Dihedral bounds for mesh generation in high dimensions

Abstract

We show that any set of n points in Rd has a Steiner Delaunay triangulation with O(n[d/2]) simplices, none of which has an obtuse dihedral angle. This result improves a naive bound of O(nd). No bound depending only on n is possible if we require the maximum dihedral angle to measure at most 90° - ϵ or the minimum dihedral to measure at least e.