Polynomial-size nonobtuse tetrahedral meshes
Let $P \subset \mathbb{R}^3$ be the closure of a bounded polyhedral domain, and let $n$ be the combinatorial complexity of its boundary: the number of its vertices, edges and faces. By a tetrahedralization of $P$ we mean a finite set of tetrahedra with pairwise disjoint interiors whose union is $P$, any two of which are disjoint or meet in a common vertex, edge or face, such that every boundary face of $P$ is a union of faces of the tetrahedra. Vertices may be added anywhere on the boundary and in the interior. It is nonobtuse if every dihedral angle of every tetrahedron is at most $\pi/2$. Bern, Mitchell and Ruppert proved that every polygonal region with $n$ vertices, holes allowed, has a nonobtuse triangulation with $O(n)$ triangles. In three dimensions, Brandts, Korotov, Křížek and Šolc record that Lenhard (1960) decomposed every tetrahedron into at most twelve path tetrahedra (tetrahedra with three mutually orthogonal edges forming a path, whose dihedral angles are all nonobtuse), though possibly not face to face. Korotov and Křížek proved that a tetrahedron with a sphere tangent to all six edges can be partitioned face to face into $24$ path tetrahedra when the centre of that sphere lies in its interior, and into $18$ when it lies on the boundary.
Problem. Are there constants $C, k > 0$ such that every such $P$ has a nonobtuse tetrahedralization with at most $C n^k$ tetrahedra? The bound may depend on nothing but $n$, in particular not on aspect ratios of $P$, and no algorithm for constructing the tetrahedralization is required.
Source: Bern, Mitchell and Ruppert (1995), in their concluding section, for three-dimensional polyhedra; restated by Bishop (2012), Question 17. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO, NA
- Keywords
- AIM Open Applied Problems, mesh generation, nonobtuse tetrahedra, triangulations
References
@article{bern1995,
author = {Bern, Marshall and Mitchell, Scott and Ruppert, Jim},
title = {Linear-size nonobtuse triangulation of polygons},
journal = {Discrete Comput. Geom.},
volume = {14},
number = {4},
year = {1995},
pages = {411--428},
doi = {10.1007/BF02570715},
}
@misc{bishop2012,
author = {Bishop, Christopher J.},
title = {Research proposal},
howpublished = {National Science Foundation proposal, Stony Brook University},
year = {2012},
url = {https://www.math.stonybrook.edu/~bishop/vita/nsf12.pdf},
note = {Question 17},
}
@article{brandts2009,
author = {Brandts, Jan and Korotov, Sergey and K{\v{r}}{\'i}{\v{z}}ek, Michal and {\v{S}}olc, Jakub},
title = {On nonobtuse simplicial partitions},
journal = {SIAM Rev.},
volume = {51},
number = {2},
year = {2009},
pages = {317--335},
doi = {10.1137/060669073},
}
@misc{korotov2026,
author = {Korotov, Sergey and K{\v{r}}{\'i}{\v{z}}ek, Michal},
title = {Two-sided bounds for dihedral angle sums of path and 4-ball tetrahedra},
year = {2026},
eprint = {2601.08304},
archivePrefix = {arXiv},
}
@misc{aim-polynomial-nonobtuse-tetrahedral-meshes,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-size nonobtuse tetrahedral meshes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/626-polynomial-nonobtuse-tetrahedral-meshes.md},
note = {Entry 626 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00373, "Polynomial-size nonobtuse tetrahedral meshes", clopen.solutions.