UniformRefinement.tex

    \subsection{Red Refinement Algorithm in 2-dimension}
    One popular refinement strategy is $red/green$ refinement proposed by R. E. Bank. The red refinement here is regular refinement which divides a triangle into four congruent smaller triangles by connecting midpoints of its three edges.\\

    \begin{figure}[h!]
    \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 red 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$.\\
    \textbf{Algorithm} Red refinement in 2D \{\\
    $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}];$\\
    \}



    \begin{lemma*}
    Red refinement gives same congruence class in 2-dimension case.
    \end{lemma*}
    \begin{proof}\mbox{}\\
    \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 for the Lemma}
    \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 red refinement produces the triangle $T_1 = [A, X, Z]$, $T_2 = [X, B, Y]$, $T_3 = [Z, Y, C]$ and $T_4 = [Y, Z, X]$. Consider the picture above.

    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 lemma above, we know that red refinement applied on a non degenerate simplex in 2 dimension gives one congruent class. Moreover, by Theorem in 3.1, we see that red refinement strategy is stable.
    [This lemma leads to stability]

    \begin{lemma*}
    Red refinement preserves consistency in 2-dimension case.
    \end{lemma*}
    \begin{proof}\mbox{}\\
    This is obvious as how simplicial complex is defined.
    \end{proof}

    %\paragraph{Stability and Consistency}\mbox{}\\
    \subsection{Stability and Consistency}
    Subdividing a triangle by connecting its midpoint, we obtain four congruent simplices $T_1, T_2, T_3$ and $T_4$. The green refinement, an irregular refinement which connects the refined edge midpoint to its opposite corner, is applied on one refined edge on which we may confront with degenerate simplices. We will never touch and refine such simplices to avoid them from degenerating.

    Clearly, the red 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 red and green refinement.

    %\paragraph{Vertices and Edges by Red Refinement in 2D}\mbox{}\\
    \subsection{Vertices and Edges by Red Refinement in 2D}
    In Figure 2 above, we see that we obtain four congruent triangles similar to the original large triangle. Lemma 1 below presents relationship between number of triangles and number of times that red refinement is applied.

    \begin{lemma}
    Denote $T_{m}$ as the number of triangles after applying red refinement m times, then,
    \begin{align*}
    T_{m+1} = 4 \cdot T_{m}, \quad T_{m} = 4^m \cdot T_0
    \end{align*}
    \end{lemma}
    \begin{proof}
    Based on Figure 3, we see that we always obtain 4 similar triangles that is same 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 3. 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 proved that $T_{m+1} = 4 \cdot T_{m}$.
    \end{proof}

    \begin{lemma}
    Denote $E_{m}$ as the number of edges of a simplicial complex $\mathcal{T}$ [Or simplex???] obtained by applying red 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*}
    \end{lemma}
    \begin{proof}
    After applying the red 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 double number of edges by bisecting edges, and obtain number of $T_m$ edges from connecting each midpoints. Therefore, we have $E_{m+1} = 2\cdot E_m + 3\cdot T_m$.\\
    The proof of the latter part can also be done by induction. The base case is obvious by Figure 3, that is $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$.\\
    Suppose that this holds after applying red refinement m times, i.e., $E_{m} = 2^{m} E_0 + 3 \cdot2^{m-1}\cdot(2^{m} -1)\cdot T_0$. Since $E_{m+1} = 2 \cdot E_m + 3 \cdot T_m$, and by the inductive hypothesis and Lemma 1, 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 of a simplicial complex $\mathcal{T}$ obtained by applying red 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}
    \begin{proof}
    Whenever red refinement is applied, we set a midpoint on each edge as a new vertex. That is, we obtain a same number of new vertices as the number of edges of the simplicial complex before applying the red refinement. After applying the red refinement one more time, the number of new vertices is same as the number of edges of $T_m$, i.e., $E_m$. Then adding together, we have $V_{m+1} = V_m + E_m$.\\
    Suppose that $V_m = V_0 + (2^m -1)\cdot E_0 + (2^{m-1} -1)(2^m -1)\cdot T_0$. Then by Lemma 2, 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\\
    &= 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\\
    &= 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 finished the proof.
    \end{proof}


    %\subsection{3D}