UniformRefinement.tex

 Based on how we preserve stability and consistency, one strategy is $\emph{red/green refinement algorithm}$, and it has been discussed by Randolph E Bank and other mathematicians\cite{bank1983some,Bey1995,zhang1995successive}. Basically, the red refinement here is regular refinement which divides a triangle into four congruent smaller triangles, and green refinement is necessary to preserve the consistency of the triangulation. $\emph{Uniform refinement}$ generally inherits its idea, but differently, it does not demand a green refinement specifically to help preserve the stability since the refinement is done simultaneously.
    
    \subsection{Uniform Refinement Algorithm in 2-dimension}
    One popular global refinement strategy is $\emph{uniform refinement}$. The main idea of uniform refinement strategy is to subdivide the triangle into four smaller triangles by connecting midpoints on each edge.

    \begin{figure}[h!]
    \centering
    \captionsetup{justification=centering}
    \begin{tikzpicture}
    \tkzDefPoint(-3.5,0){A''}
    \tkzDefPoint(-2,2){B''}
    \tkzDefPoint(-1,0){C''}
    \tkzDrawSegments(A'',B'' B'',C'' A'',C'')

    \tkzDefPoint(0,0){A}
    \tkzDefPoint(1.5,2){B}
    \tkzDefPoint(2.5,0){C}
    \tkzDrawSegments(A,B B,C A,C)

    \tkzDefMidPoint(A,B) \tkzGetPoint{ab}
    \tkzDefLine[orthogonal=through ab](A,B)
    \tkzDefMidPoint(A,C) \tkzGetPoint{ac}
    \tkzDefLine[orthogonal=through ac](A,C)
    \tkzDefMidPoint(B,C) \tkzGetPoint{bc}
    \tkzDefLine[orthogonal=through bc](B,C)
    \tkzDrawSegment(ab,ac)
    \tkzDrawSegment(ab,bc)
    \tkzDrawSegment(ac,bc)

    \tkzDefPoint(3.5,0){A'}
    \tkzDefPoint(5,2){B'}
    \tkzDefPoint(6,0){C'}
    \tkzDrawSegments(A',B' B',C' A',C')
    \tkzDefMidPoint(A',B') \tkzGetPoint{ab'}
    \tkzDefLine[orthogonal=through ab'](A',B')
    \tkzDefMidPoint(A',C') \tkzGetPoint{ac'}
    \tkzDefLine[orthogonal=through ac'](A',C')
    \tkzDefMidPoint(B',C') \tkzGetPoint{bc'}
    \tkzDefLine[orthogonal=through bc'](B',C')
    \tkzDrawSegment(ab',ac')
    \tkzDrawSegment(ab',bc')
    \tkzDrawSegment(ac',bc')

    \tkzDefMidPoint(A',ab') \tkzGetPoint{aab}
    \tkzDefLine[orthogonal=through aab](A',ab')
    \tkzDefMidPoint(A',ac') \tkzGetPoint{aac}
    \tkzDefLine[orthogonal=through aac](A',ac')
    \tkzDefMidPoint(ac',ab') \tkzGetPoint{x}
    \tkzDefLine[orthogonal=through x](ac',ab')
    \tkzDrawSegment(aab,aac)
    \tkzDrawSegment(aab,x)
    \tkzDrawSegment(aac,x)

    \tkzDefMidPoint(B',ab') \tkzGetPoint{abb}
    \tkzDefLine[orthogonal=through abb](B',ab')
    \tkzDefMidPoint(B',bc') \tkzGetPoint{bbc}
    \tkzDefLine[orthogonal=through bbc](B',bc')
    \tkzDefMidPoint(bc',ab') \tkzGetPoint{y}
    \tkzDefLine[orthogonal=through y](bc',ab')
    \tkzDrawSegment(abb,bbc)
    \tkzDrawSegment(abb,y)
    \tkzDrawSegment(bbc,y)

    \tkzDefMidPoint(C',ac') \tkzGetPoint{acc}
    \tkzDefLine[orthogonal=through acc](C',ac')
    \tkzDefMidPoint(C',bc') \tkzGetPoint{bcc}
    \tkzDefLine[orthogonal=through bcc](C',bc')
    \tkzDefMidPoint(bc',ac') \tkzGetPoint{z}
    \tkzDefLine[orthogonal=through z](bc',ac')
    \tkzDrawSegment(acc,bcc)
    \tkzDrawSegment(acc,z)
    \tkzDrawSegment(bcc,z)

    \tkzDefMidPoint(ab',ac') \tkzGetPoint{l}
    \tkzDefLine[orthogonal=through l](ab',ac')
    \tkzDefMidPoint(ab',bc') \tkzGetPoint{m}
    \tkzDefLine[orthogonal=through m](ab',bc')
    \tkzDefMidPoint(ac',bc') \tkzGetPoint{r}
    \tkzDefLine[orthogonal=through r](ac',bc')
    \tkzDrawSegment(l,m)
    \tkzDrawSegment(l,r)
    \tkzDrawSegment(m,r)

    \end{tikzpicture}
    \caption{Illustration of uniform refinement\\Starting with a single triangle and two successive refinement steps.}
    \label{Fig3}%change all after!!!
    \end{figure}

    Let $T = [x^0, x^1, x^2]$ be the triangle to be refined, and denote $x^{ij}$ by the midpoint of the edge between $x^i$ and $x^j$ for $0\leq i < j\leq 2$.
    Uniform refinement of $T$ produces the four new tetrahedra
    \begin{align*}
    T_1 &:= [x^0, x^{01}, x^{02}], & \qquad T_2 &:= [x^{01}, x^{1}, x^{12}],\\
    T_3 &:= [x^{02}, x^{12}, x^2], &\qquad T_4 &:= [x^{01}, x^{12}, x^{02}].\\
    \end{align*}
    



    \begin{lemma}
    The triangle $T_1, T_2, T_3$ and $T_4$ produced by the uniform refinement have the same congruence class as $T$.
    %Uniform refinement gives same congruence class in 2-dimension case.
    \label{lma1}
    \end{lemma}
    \begin{proof}
    \begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.8]
    \tkzDefPoint(0,0){A}
    \tkzDefPoint(1.5,2){B}
    \tkzDefPoint(2.5,0){C}
    \tkzDrawSegments(A,B B,C A,C)

    \tkzLabelPoints[above,yshift=0pt](B)
    \tkzLabelPoints[left,yshift=4pt](A)
    \tkzLabelPoints[right,yshift=4pt](C)
    \tkzDefMidPoint(A,B) \tkzGetPoint{X}
    \tkzDefLine[orthogonal=through ab](A,B)
    \tkzDefMidPoint(A,C) \tkzGetPoint{Z}
    \tkzDefLine[orthogonal=through ac](A,C)
    \tkzDefMidPoint(B,C) \tkzGetPoint{Y}
    \tkzDefLine[orthogonal=through bc](B,C)
    \tkzDrawSegment(X,Z)
    \tkzDrawSegment(X,Y)
    \tkzDrawSegment(Z,Y)
    \tkzLabelPoints[above,xshift=-2mm](X)
    \tkzLabelPoints[above,xshift=2mm](Y)
    \tkzLabelPoints[below](Z)
    \end{tikzpicture}
    \caption{Illustration of Uniform Refinement as in the proof of Lemma~\ref{lma1}}
    \label{Fig4}
    \end{figure}

    Let A, B, C be the vertices of the triangle $T$ and let X, Y, Z be the midpoints of the edge AB, BC and AC. An application of uniform refinement produces the triangles $T_1 = [A, X, Z]$, $T_2 = [X, B, Y]$, $T_3 = [Z, Y, C]$ and $T_4 = [Y, Z, X]$. See Figure \ref{Fig4}.

    We have line XY parallel to line AC, i.e., $XY \parallel AC$, so $\angle{BXY} = \angle{XAZ}$. Similarily, since $XZ\parallel BC$, we have $\angle{XBY} = \angle{AXZ}$. Since X is the midpoint of line AB, then $|AX| = |BX|$. In short, we have 
    \begin{align*}
    \angle{BXY} = \angle{XAZ},
    \quad
    |BX| = |AX|,
    \quad
    \angle{XBY} = \angle{AXZ}.
    \end{align*}
    Therefore, $\triangle{BXY} \cong \triangle{XAZ}$. Similarily, we can prove the four triangles are congruent to each other, i.e., $\triangle{BXY}\cong\triangle{XAZ}\cong\triangle{YZC} \cong\triangle{ZYX}$, so they are in a same congruent class, which is same as the one of the original triangle $\triangle{BAC}$.
    \end{proof}
    By the \cref{lma1}, we know that uniform refinement applied on a non-degenerate simplex in 2 dimensions gives one congruence class. Moreover, by Theorem in 3.1, we see that the uniform refinement strategy is stable.

    \begin{lemma}
    Uniform refinement preserves consistency in the 2-dimensional case.
    \label{lma2}
    \end{lemma}
    %\begin{proof}\mbox{}\\
    %This is obvious as how simplicial complex is defined.
    %\end{proof}

    %\paragraph{Stability and Consistency}\mbox{}\\

    Clearly, the uniform refinement strategy is stable since it produces a finite number of triangles congruent to the original simplex. Meanwhile, we preserve consistency by bisecting triangles with one refined edge and never refine them any further. Therefore, we obtain stability and consistency through uniform refinement.

    %\paragraph{Vertices and Edges by Red Refinement in 2D}\mbox{}\\
    \subsection{Counting Vertices and Edges by Uniform Refinement}
    In Figure \ref{Fig4}, we see that we obtain four congruent triangles similar to the original large triangle. The \cref{lma3} below presents relationship between the number of triangles and number of times that uniform refinement is applied.

    \begin{lemma}
    Let $T_{m}$ be the number of triangles after applying uniform refinement m times. Then,
    \begin{align*}
    T_{m+1} = 4 \cdot T_{m}, \quad T_{m} = 4^m \cdot T_0.
    \end{align*}
    \label{lma3}
    \end{lemma}
    \begin{proof}
    Based on Figure \ref{Fig3}, we see that we always obtain 4 similar triangles that are in the same congruence class as the original one. In other words, we have $T_{m+1} = 4 \cdot T_{m}$.

    To prove $T_{m} = 4^m \cdot T_0$ by induction, we have the base case that $T_1 = 4^1 \cdot T_0$ in Figure \ref{Fig3}. Suppose that this is true for $T_{m} = 4^m \cdot T_0$, we need to prove this holds true for $T_{m+1}$.\\
    Since we have $T_{m+1} = 4 \cdot T_{m}$, and by inductive hypothesis, we have
    \begin{align*}
    T_{m+1} = 4 \cdot T_{m} = 4 \cdot (4^m\cdot T_0) = 4^{m+1}\cdot T_0.
    \end{align*}
    Therefore, by induction, we have proved that $T_{m+1} = 4 \cdot T_{m}$.
    \end{proof}

    \begin{lemma}
    Let $E_{m}$ be the number of edges after applying uniform refinement m times. Then,
    \begin{align*}
    E_{m+1} = 2 \cdot E_m + 3 \cdot T_m, \quad E_{m} = 2^{m}\cdot E_0 + 3 \cdot2^{m-1}\cdot(2^{m} -1)\cdot T_0.
    \end{align*}
    \label{lma4}
    \end{lemma}
    \begin{proof}
    After applying the uniform refinement one more time, that is $m+1$ times in total, then we can think like in each smaller triangle in $T_m$, we again have a double number of edges by bisecting edges, and obtain the number of $T_m$ edges from connecting each midpoint. Therefore, we have $E_{m+1} = 2\cdot E_m + 3\cdot T_m$.

    The proof of the second equation can be done by induction. The base case is obvious by Figure \ref{Fig3}, that is
    \begin{align*}
    E_1 &= 9 \\
    &= 2^1\cdot 3 + 3\cdot 2^0 \cdot (2^1 - 1)\cdot1\\
    &= 2^1\cdot E_0 + 3\cdot2^{1-1}\cdot(2^1 - 1)\cdot T_0.
    \end{align*}
    Suppose that this holds after applying uniform refinement $m$ times, i.e.
    \begin{align*}
    E_{m} = 2^{m} E_0 + 3 \cdot2^{m-1}\cdot(2^{m} -1)\cdot T_0.
    \end{align*}, 
    since $E_{m+1} = 2 \cdot E_m + 3 \cdot T_m$, and by the inductive hypothesis and \cref{lma3}, we have
    \begin{align*}
    E_{m+1} &= 2 \cdot E_m + 3 \cdot T_m \\
    &= 2(2^{m}\cdot E_0 + 3 \cdot2^{m-1}\cdot(2^{m} -1)\cdot T_0) + 3\cdot 4^m\cdot T_0\\
    &= 2^{m+1}\cdot E_0 + 3\cdot2^m\cdot(2^m - 1)\cdot T_0 + 3\cdot4^m\cdot T_0\\
    &= 2^{m+1}\cdot E_0 + 3\cdot(2^m\cdot(2^m -1 + 2^m))\cdot T_0\\
    &=2^{m+1}\cdot E_0 + 3\cdot2^m\cdot(2^{m+1}-1)\cdot T_0.
    \end{align*}
    Thus, we finished the proof by induction.
    \end{proof}

    \begin{lemma}
    Denote $V_{m}$ as the number of vertices after applying uniform refinement m times, then,
    \begin{align*}
    V_{m+1} = V_{m} + E_{m}, \quad V_m = V_0 + (2^m -1)\cdot E_0 + (2^{m-1}\cdot(2^m+3)-2)\cdot T_0.
    \end{align*}
    \end{lemma}
    \label{lma5}
    \begin{proof}
    Whenever uniform refinement is applied, we set a midpoint on each edge as a new vertex. That is, the number of new vertices is the number of edges of the simplicial complex before applying the uniform refinement. Then adding together, we have $V_{m+1} = V_m + E_m$.

    %Suppose that 
    %\begin{align*}
    %V_m = V_0 + (2^m -1)\cdot E_0 + (2^{m-1} -1)(2^m -1)\cdot T_0
    %\end{align*} 
    We now prove the other equality. By using Lemma \cref{lma4} repeatedly, we have
    \begin{align*}
    V_{m+1} &= V_m + E_m\\
    &= V_m + 2^m\cdot E_0 + 3\cdot 2^{m-1}\cdot(2^m-1)\cdot T_0\\
    &= V_0 + \sum_{k=0}^m 2^k E_0 + 3\cdot 2^{k-1}\cdot(2^k-1)\cdot T_0.\\
    \intertext{Expanding, $3\cdot 2^{k-1}\cdot(2^k-1) = 3\cdot2^{k-1+k} + 3\cdot2^{k-1}$, we have}
    &= V_0 + \sum_{k=0}^m 2^k E_0 + 3\sum_{k=0}^m 2^{2k-1}\cdot T_0 + 3\sum_{k=0}^m 2^{k-1}\cdot T_0\\
    &= V_0 + (2^{m+1}-1)E_0 + \frac{3}{2}\sum_{k=0}^m 4^k\cdot T_0 + \frac{3}{2}\sum_{k=0}^m 2^k\cdot T_0.\\
    \intertext{Since $\sum_{k=0}^m a^k = \frac{a^{m+1}-1}{a-1}$, we then have}
    &= V_0 + (2^{m+1}-1)E_0 + \frac{3}{2}\cdot\frac{4^{m+1}-1}{3}\cdot T_0 + \frac{3}{2}(2^{m+1}-1)\cdot T_0\\
    &= V_0 + (2^{m+1}-1)E_0 + \frac{4^{m+1}-1 + 3\cdot2^{m+1} -3}{2}\cdot T_0\\
    &= V_0 + (2^{m+1}-1)E_0 + (2^m\cdot(2^{m+1}+3)-2)\cdot T_0.
    \end{align*}
    Thus, we have finished the proof.
    \end{proof}


    %\subsection{3D}