Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement

Abstract

We prove, to our knowledge, the first unconditional cumulative closure estimates for the Arnold--Mukherjee--Pouly (AMP) refinement algorithm and the original face-marked tetrahedral algorithm of Bänsch on arbitrary conforming initial tetrahedral meshes. Let $T_0,\dots ,T_L$ be an adaptive mesh sequence generated by either algorithm, with $M_{\ell }\subseteq T_{\ell }$ denoting the marking set at step $\ell$. Then $$\#T_L-\#T_0\le C_{\mathrm{clos}}(T_0)\sum _{\ell =0}^{L-1}\#M_{\ell }.$$ The proof is intrinsic to the physical three-dimensional mesh and requires neither an initial compatibility condition nor a higher-dimensional embedding. It organizes conformity refinements into a causal forest and combines a uniform horizontal-propagation estimate with a weighted packing argument to obtain an explicit closure constant. For the original Bänsch algorithm, every history-dependent resolution of the initial two-edge ambiguity is represented by one of finitely many AMP histories. The estimate therefore holds uniformly for arbitrary deterministic or nondeterministic choices. This resolves a long-standing complexity question for the Bänsch--AMP family.

38 pages