Termination and cumulative complexity of NVB conformity closure

For a current cell $K$, follow its interior reference-edge neighbor. The common label is $g(K)$; by [F1] the neighbor either has the same generation, giving a compatibly divisible pair, or has generation $g(K)-1$. Continue in the latter case. Strict generation drops terminate at a boundary reference edge or compatible pair. Refine from that terminal end and re-inspect each earlier pending leaf, as the algorithm prescribes. A coarser neighbor may need two bisections: after its reference-edge split, the child containing the pending common edge has that inherited edge as reference and is bisected before returning to $K$. These are children or grandchildren of a chain cell $L$; for a coarser chain cell $g(L)\le g(K)-1$, so their generations are at most $g(K)+1$. The terminal partner and $K$ itself need one split. Each processed common edge is split on both sides, so the resulting mesh is conforming. The finite chain and this finite reinspection give termination for one request, and the finitely many requested descendant generations give termination of a complete call.

Let $g(K)$ denote generation. Each bisection halves area, and [F2] gives constants $c_0,C_0>0$ depending only on the finitely many initial shapes such that $c_0{2}^{-g(K)}\le \mathrm{\mid }K\mathrm{\mid }\le C_0{2}^{-g(K)}$ and $\mathrm{diam}K\le C_0{2}^{-g(K)\mathrm{/}2}$. In the backward chain of step 1.1 there is at most one cell at each generation, plus at most one terminal compatible partner. Hence the sum of diameters from generation $g_{\min }$ upward is at most $D_0{2}^{-g_{\min }\mathrm{/}2}$ with $D_0=2C_0\mathrm{/}(1-2^{-1\mathrm{/}2})$. Every created cell is a child of $K$ or its terminal same-generation partner, or a child or grandchild of a strictly coarser chain cell. Step 1.1 therefore gives $g(T)\le g(K)+1$. For a created cell $T$ within an original chain cell $L$, the portion of the chain between $K$ and $L$ has its lowest generation $g(L)$; summing its diameters gives $\mathrm{dist}(K,T)\le D_1{2}^{-g(T)\mathrm{/}2}$ with $D_1=4D_0$. The chain is finite by the integer generation drop, and these estimates supply the geometric radius used below.

First consider one-generation requests in a finite sequence and let $\mathcal{M}$ be the union of all requested cells. For a final cell $T$ and marked cell $T^{\ast }$ define a nonnegative allocation $\lambda (T,T^{\ast })=\{\begin{array}{ll}a(g(T^{\ast })-g(T)),& \mathrm{dist}(T,T^{\ast })<DB{2}^{-g(T)\mathrm{/}2}\text{ and }g(T)\le g(T^{\ast })+1,\\ 0,& \text{otherwise},\end{array}$ where $a(\mathrm{\ell })=(\mathrm{\ell }+2{)}^{-2}$ for $\mathrm{\ell }\ge -1$, $b(\mathrm{\ell })=2^{\mathrm{\ell }\mathrm{/}3}$ for $\mathrm{\ell }\ge 0$, $A={\sum }_{\mathrm{\ell }\ge -1}a(\mathrm{\ell })<\mathrm{\infty }$, $B={\sum }_{\mathrm{\ell }\ge 0}{2}^{-\mathrm{\ell }\mathrm{/}2}b(\mathrm{\ell })<\mathrm{\infty }$, and $D=2D_1+2C_0$, with $D_1$ from step 2.1. The series for $B$ is geometric with ratio $2^{-1\mathrm{/}6}<1$, and $c_{\ast }={\inf }_{\mathrm{\ell }\ge 1}a(\mathrm{\ell })b(\mathrm{\ell })>0$ because $2^{\mathrm{\ell }\mathrm{/}3}\mathrm{/}(\mathrm{\ell }+2{)}^2$ tends to infinity.

Fix $T^{\ast }\in \mathcal{M}$ with generation $g^{\ast }$. At a fixed generation $g\le g^{\ast }+1$, cells with nonzero allocation lie in a ball of radius $DB{2}^{-g\mathrm{/}2}$ about $T^{\ast }$. Each has area at least $c_0{2}^{-g}$ by step 2.1, while that ball enlarged by one cell diameter has area at most $C_D{2}^{-g}$. Since cell interiors are disjoint, their number is at most a constant $N_D$ independent of $g,T^{\ast }$, and the final level. Summing weights over generations therefore gives ${\sum }_{T\in {\mathcal{T}}_n\setminus {\mathcal{T}}_0}\lambda (T,T^{\ast })\le N_D{\sum }_{\mathrm{\ell }\ge -1}a(\mathrm{\ell })=N_{D}A=:C_1\mathrm{.}$

Fix a new cell $T_0$ in the final forest. Trace its unique parent backward through the finite refinement history. If the parent was created during closure, take the least-ID requested cell whose recursive chain created it; repeat this at each earlier creation time. This gives a finite sequence of requested cells $T_1,\dots ,T_J$ ending at an initial cell. Step 2.1 gives $g(T_{j+1})\ge g(T_j)-1$ and, for each consecutive pair in the sequence, $\mathrm{dist}(T_{j-1},T_j)\le D_1{2}^{-g(T_{j-1})\mathrm{/}2}$. Let $s$ be the first index with $g(T_s)=g(T_0)-1$. The prefix whose links join $T_0$ to $T_s$ is $T_0,\dots ,T_{s-1}$; each of its generations is $g(T_0)+\mathrm{\ell }$ for some $\mathrm{\ell }\ge 0$. The triangle inequality for set distances includes the diameters of the intervening cells. Steps 2.1 and the diameter bound control the sum by $(D_1+C_0)$ times the corresponding generation sum; $D=2(D_1+C_0)$ leaves strict slack. Consequently, if this prefix has at most $b(\mathrm{\ell })$ cells at every generation $g(T_0)+\mathrm{\ell }$, then $\mathrm{dist}(T_0,T_s)<DB{2}^{-g(T_0)\mathrm{/}2}\mathrm{.}$ Thus the terminal requested cell $T_s$ lies in the allocation radius and contributes $a(-1)>0$. Otherwise let $j_{\ast }$ be the first prefix with more than $b({\mathrm{\ell }}_{\ast })$ cells at some generation $g(T_0)+{\mathrm{\ell }}_{\ast }$. Every earlier link prefix satisfies the displayed distance bound. If ${\mathrm{\ell }}_{\ast }=0$, since $T_0$ is new and $b(0)=1$, at least one other cell of that generation is a marked cell and contributes $a(0)$. If ${\mathrm{\ell }}_{\ast }>0$, all cells of that generation in the prefix are marked; each lies within the allocation radius and contributes $a({\mathrm{\ell }}_{\ast })$. In this case their total is greater than $a({\mathrm{\ell }}_{\ast })b({\mathrm{\ell }}_{\ast })\ge c_{\ast }$. Hence every new cell receives at least $C_2=\min \{a(-1),a(0),c_{\ast }\}>0$ allocation.

Sum the lower bound from step 3.3 over new cells and interchange the two finite sums. The upper bound from step 3.2 gives $C_2(\mathrm{\#}{\mathcal{T}}_n-\mathrm{\#}{\mathcal{T}}_0)\le {\sum }_{T^{\ast }\in \mathcal{M}}{\sum }_{T\mathrm{\notin }{\mathcal{T}}_0}\lambda (T,T^{\ast })\le C_1\mathrm{\#}\mathcal{M}\mathrm{.}$ For three requested generations, view each parent in $Q_k$ as successive one-generation requests. There are at most $2^{j-1}\mathrm{\#}{Q}_k$ virtual requests at stage $j=1,2,3$, even if closure performs some requested splits before their scheduled turn. The total is at most $7\mathrm{\#}{Q}_k$, giving $C_{\mathrm{g}\mathrm{e}\mathrm{n}}=7C_1\mathrm{/}{C}_2$. For the algorithm, every original triangle has at most three edge neighbors, so $\mathrm{\#}{Q}_k\le 4\mathrm{\#}{M}_k$; hence $C_{\mathrm{c}\mathrm{l}}=28C_1\mathrm{/}{C}_2$ proves the displayed estimate in terms of the unchanged bulk marks. Empty marks give no requests or splits, and all bisections, including those needed for patch expansion and conformity, are counted.