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 T0,…,TL be an adaptive mesh sequence generated by either algorithm, with Mℓ⊆ Tℓ denoting the marking set at step ℓ. Then #TL−#T0≤ Cclos(T0)∑ℓ=0L−1#Mℓ. 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.
Related
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Closure complexity of longest-edge bisection for triangular meshes
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
- Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
BibTeX
@misc{li2026closure,
title = {{Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement}},
author = {Yuwen Li and Zhiyuan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29616},
eprint = {2609.29616},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29616},
}
RIS
TY - UNPB
TI - Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement
AU - Yuwen Li
AU - Zhiyuan Yang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29616
UR - https://arxiv.org/abs/2609.29616
AB - 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,…,T_L be an adaptive mesh sequence generated by either algorithm, with M_ℓ⊆ T_ℓ denoting the marking set at step ℓ. Then #T_L−#T_0≤ C_clos(T_0)∑_ℓ=0^L−1#M_ℓ. 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.
ER -