\input header
\input epsf

\title{Subdivision Curve Definition and Analysis Exercises}

\section{Definition by Box-splines}

\subsection{Determine the stencils for the binary univariate box-splines of degrees 3, 4 and 5}

The stencils are the rows of the matrix, and the generating function approach gives us the columns.

\pop degree 3  

The generating function is $(1+z)^4/2^3 = (1+4z+6z^2+4z^3+z^4)/8$ and so the matrix is like
$$\matrix{
6&1&\cr
4&4&\cr
1&6&1\cr
&4&4&\cr
&1&6&1\cr}$$

and so the distinct stencils are [1, 6, 1]/8 and [4, 4]/8.

\filbreak
\pop degree 4

The generating function is $(1+z)^5/2^4 = (1+5z+10z^2+10z^3+5z^4+z^5)/8$ 
and so the matrix is like
$$\matrix{
10&5&\cr
5&10&1\cr
1&10&5\cr
&5&10&1\cr
&1&10&5\cr}$$

and so the distinct stencils are [1, 5, 10]/16 and [10, 5, 1]/16.

\filbreak
\pop degree 5

The generating function is $(1+z)^6/2^5 = (1+6z+15z^2+20z^3+15z^4+6z^5+z^6)/32$ 
and so the matrix is like
$$\matrix{
15&15&1\cr
 6&20&6\cr
 1&15&15&1\cr
  & 6&20&6\cr
  & 1&15&15\cr}$$

and so the distinct stencils are [6, 20, 6]/32 and [1,15,15,1]/32.

\subsection{Determine the quarternary (arity=4) box spline of degree 2.}

\pop

The generating function is $(1+z+z^2+z^3)^3/4^2 = (1+3z+6z^2+10z^3+12z^4+12z^5+10z^6+6z^7+3z^8+z^9)/16$ 
and so the matrix is like
$$\matrix{
12&1&\cr
12&3&\cr
10&6&\cr
 6&10&\cr
 3&12&1\cr
 1&12&3\cr
  &10&6\cr
  &6&10\cr
  &3&12\cr
  &1&12\cr
}$$


and so the distinct stencils are [6, 10]/16, [10,6]/16, [1,12,3]/16 and [3,12,1]/16.

\section{Dubuc-Deslauriers interpolating refinements}

\subsection{Determine the masks for the binary 4-pt and 6-pt schemes}

In the D-D schemes, the new intermediate vertices are determined by Lagrange interpolation, which passes a single polynomial through the influencing points.  The stencils are therefore given by the linear combinations from Lagrange interpolation.

\pop 4-pt scheme

To get the first coefficient we have to determine the lagrange interpolant at 1.5 of the polynomial through [0,1],[1,0],[2,0] and [3,0].

This polynomial can be written as
$$\lambda(x-1)(x-2)(x-3)$$ because it has roots at 1,2,3.   The coefficient $lambda$ is determined by the value at $x=0$, $lambda(-1)(-2)(-3) = 1$

Thus the value at $x=1.5$ is just
$${{(1.5-1)(1.5-2)(1.5-3)}\over{-6}} = .5(-.5)(-1.5)/6 = -1/16$$

By symmetry the last coefficient has the same value, and since Lagrange interpolation has constant precision, the coefficients must sum to unity.  We therefore have the stencil
$$[-1,9,9,-1]/16$$

When this stencil  and the unit stencil from the interpolated point are assembled into a matrix,we find
$$\matrix{
0&16\cr
-1&9&9&-1\cr
&0&16\cr
&-1&9&9&-1\cr
&&0&16\cr
&&-1&9&9&-1\cr
&&&0&16\cr
&&&-1&9&9&-1\cr
}$$

so the mask is $[-1, 0, 9, 16, 9, 0, -1]/16$

\filbreak
\pop 6-pt scheme

We need to determine two of the coefficients before being able to invoke symmetry and summing to 1 easily.

The end coefficient is given by the lagrange polynomial
$${{(x-1)(x-2)(x-3)(x-4)(x-5)}\over{(-1)(-2)(-3)(-4)(-5)}}$$ at $x=2.5$
$$1.5*.5*(-.5)*(-1.5)*(-2.5)/(-5!) = 3*3*5/2^5*5! = 3/256$$

The next coefficient is given by the lagrange polynomial
$${{(x)(x-2)(x-3)(x-4)(x-5)}\over{(1-0)(1-2)(1-3)(1-4)(1-5)}}$$ at $x=2.5$
$${{2.5*.5*(-.5)(-1.5)(-2.5)}\over{4!}}= -{{5*3*5}\over{2^5*4!}} = -25/256$$

The remaining coefficient must be given by $(1/2+25/256-3/256) = 150/256$, so that the stencil is [3,-25,150,150,-25,3]/256.

The matrix becomes
$$\matrix{
0&0&256\cr
3&-25&150&150&-25&3\cr
&0  &0  &256&0&0\cr
&3&-25&150&150&-25&3\cr
&&0  &0  &256&0&0\cr
&&3&-25&150&150&-25&3\cr
&&&0  &0  &256&0&0\cr
&&&3&-25&150&150&-25&3\cr
&&&&0  &0  &256&0&0\cr
&&&&3&-25&150&150&-25&3\cr
&&&&&0  &0  &256&0&0\cr
}$$
and so the mask is [3,0,-25,0,150,256,150,0,-25,0,3]/256



\subsection{Determine the mask for the Dubuc-Deslauriers ternary 4-pt scheme}

This requires evaluation at $x=4/3$ of 
$$\eqalign{
{{(x-1)(x-2)(x-3)}\over{(-1)(-2)(-3)}} &= {{-(1/3)(-2/3)(-5/3)}\over{6}} = -5/81 \cr
{{(x-0)(x-2)(x-3)}\over{(1)(-1)(-2)}} &= {{(4/3)(-2/3)(-5/3)}\over{2}} = 60/81 \cr
{{(x-0)(x-1)(x-3)}\over{(2)(1)(-1)}} &= {{-(4/3)(1/3)(-5/3)}\over{2}} = 30/81 \cr
{{(x-0)(x-1)(x-2)}\over{(3)(2)(1)}} &= {{(4/3)(1/3)(-2/3)}\over{6}} = -4/81 \cr}$$

The values at $x=5/3$ are just the same in reverse sequence, by symmetry.

The matrix is
$$\matrix{
-5&60&30&-4\cr
-4&30&60&-5\cr
&&81\cr
&-5&60&30&-4\cr
&-4&30&60&-5\cr
&&&81\cr
&&-5&60&30&-4\cr
&&-4&30&60&-5\cr
&&&&81\cr
&&&-5&60&30&-4\cr
&&&-4&30&60&-5\cr
&&&&81\cr
&&&&-5&60&30&-4\cr
&&&&-4&30&60&-5\cr
}$$

and so the mask is [-4,-5,0,30,60,81,60,30,0,-5,-4]/81

\section{z-transform analysis of convergence}

\firstsubsection {Making a difference mask}

The z-transform approach to analysing continuity and convergence shows how, given a subdivision mask, a derived mask can be computed, which relates differences of the subdivided polygon to those of the original.

$$S'(z) = {{(1-z)}\over{(1-z^a)}}S(z)$$

This form begs the question of whether $(1-z)S(z)$ is actually divisible without remainder by $(1-z^a)$.   If it is not, then the above expression does not give a Laurent Polynomial.

\pop Prove that if a scheme $S$ has constant precision, $(1-z)S(z)$ is exactly divisible by $(1-z^a)$

\pop Prove that if a scheme $S$ has both constant precision and (functional) linear precision, we may construct derived schemes for both first and second differences.

\theorem {If a scheme $S$ has constant precision, $(1-z)S(z)$ is exactly divisible by $(1-z^a)$
}

\given a scheme $S$ such that each of the stencils sums to unity

\toprove that $(1-z)S(z)$ is exactly divisible by $(1-z^a)$

\proof  consider the explicit long division

$$1 - z^a\  |\overline{\ s_0 + s_1z + s_2z^2\ldots + s_az^a + \ldots + s_{2a}z^{2a}+\ldots}$$


The division process operates essentially independently on the groups of powers modula $a$.

$$\matrix{1 - z^a\  |\cr
\ \cr \ \cr\ \cr\ \cr \ \cr}\overline{\matrix{
s_0 &+\ldots &+& s_az^a &+\ldots &+&s_{2a}z^{2a}&+\ldots&+&s_{na}z^{na}\cr
s_0 &&-&s_0z^a\cr
&&&\overline{(s_0+s_a)z^a}&&+&s_{2a}z^{2a}\cr
&&&(s_0+s_a)z^a&&-&(s_0+s_a)z^{2a}\cr
&&&&&&\overline{(s_0+s_a+s_{2a})z^{2a}}\cr
&&&&&&&&&\overline{\sum_i s_{ia}z^{na}}\cr
}}$$

Each such group contributes a term to the remainder, and the terms so added are essentially the sums of the stencils.  By linear precision these all sum to 1.

The net remainder at this stage is therefore $z^q(1+z+z^2+\ldots+z^{a-1}$

However the product of this with the $(1-z)$ factor of the numerator is exactly $1-z^a$ and so there is no remainder when the whole numerator is divided by $1-z^a$.

\endtheorem 

\theorem{If a scheme $S$ has both constant and (functional) linear precision, we may construct derived schemes for both first and second differences.}

\given a scheme $S$ of width $w$ and arity $a$, such that each stencil sums to unity, ($\sum_j s_j = 1$) where $j$ selects the coefficients in a row of the matrix, and such that $\sum_j (j-(w-1)/2)s_j = 0$

\toprove that $(1-z)S(z)$ is exactly divisible by $1-z^a$ and that $(1-z)^2S(z)$ is exactly divisible by $(1-z^a)^2$.

\construction Let $S'(z) = a(1-z)S(z)/(1-z^a)$

\proof We know the first part of the theorem by the previous result.  Thus $S'(z)$ is a well defined scheme.

Now if a scheme has functional linear precision, its derivative scheme must have constant precision.  This is obvious from the consideration that if we apply it to a set of data lying on a straight line, where all the first differences are equal, the refined polygon will also have the property that all the first differences are equal.  Factored by the 
arity, (so that they track the first derivative) the new values are equal to the old.  This factor is a constant, and so does not influence divisibility.

So, by the previous theorem $(1-z)S'(z)$ is divisible by $(1-z^a)$, but this is exactly
$a(1-z)^2S(z)/(1-z^a)$ and so $(1-z)^2S(z)$ is exactly divisible by $(1-z^a)^2$.

\endtheorem

\section{Eigenanalysis}

\firstsubsection{Carry out the odd and even eigenanalyses for [1,4,4,1]/5} 

The matrix permuted so that the vertices are sequenced into ascending order of distance from the mark point at the middle of a span is 

$$5\left\lceil\matrix{
A'\cr B'\cr C'\cr D'\cr E'\cr F'\cr\vdots}\right\rceil
=
\left\lceil\matrix{
4&1\cr
1&4\cr
4&0&1\cr
&4&0&1\cr
1&0&4\cr
&1&0&4\cr
&&&&\ddots}\right\rceil
\left\lceil\matrix{
A\cr B\cr C\cr D\cr E\cr F\cr\vdots}\right\rceil
$$

Taking the even part, by assuming that $A=B$, $C=D$ ... gives
$$5\left\lceil\matrix{
A'\cr C'\cr E'\cr\vdots}\right\rceil
=
\left\lceil\matrix{
5&\cr
4&1\cr
1&4\cr
&&\ddots}\right\rceil
\left\lceil\matrix{
A\cr C\cr E\cr\vdots}\right\rceil
$$

whose eigencomponents are 
$$\left\lceil\matrix{
1\cr1\cr1\cr\vdots}\right\rceil \matrix{1 \cr\  \cr\ \cr\ }
\matrix{[\matrix{1&0}]\cr\ \cr\ \cr\ }
\hbox{\qquad and \qquad}
\left\lceil\matrix{
0\cr1\cr4\cr\vdots}\right\rceil \matrix{1/5 \cr\  \cr\ \cr\ }
\matrix{[\matrix{-1&1}]\cr\ \cr\ \cr\ }
$$

Mapping the eigenvectors back into the natural sequence along the polygon gives
$$[\ldots,1,1,1,1,1,1,\ldots]\hbox{ and }[\ldots,4,1,0,0,1,4,\ldots],$$ 
the latter of which is not a quadratic variation.

Taking the odd part, by assuming that $-A=B$, $-C=D$ ... gives
$$5\left\lceil\matrix{
A'\cr C'\cr E'\cr\vdots}\right\rceil
=
\left\lceil\matrix{
3&\cr
4&1\cr
1&4\cr
&&\ddots}\right\rceil
\left\lceil\matrix{
A\cr C\cr E\cr\vdots}\right\rceil
$$

whose eigencomponents are 
$$\left\lceil\matrix{
1\cr2\cr-1\cr\vdots}\right\rceil \matrix{3/5 \cr\  \cr\ \cr\ }
\matrix{[\matrix{3/5&0}]\cr\ \cr\ \cr\ }
\hbox{\qquad and \qquad}
\left\lceil\matrix{
0\cr1\cr4\cr\vdots}\right\rceil \matrix{1/5 \cr\  \cr\ \cr\ }
\matrix{[\matrix{-1&1}]\cr\ \cr\ \cr\ }
$$
Mapping the eigenvectors back into the natural sequence along the polygon gives
$$[\ldots,1,-2,-1,1,2,-1,\ldots]\hbox{ and }[\ldots,4,1,0,0,-1,-4,\ldots],$$
 the former of which is very hard to interpret.


 

\subsection{Carry out the odd and even eigenanalyses for [-1,0,9,16,9,0,-1]/16} 

The part of the matrix contributing to the eigensystem for the even part is
$$\left\lceil\matrix{
16&0&0&0\cr
9&8&-1&0\cr
0&16&0&0\cr
-1&9&9&-1\cr}\right\rceil/16$$
The eigenvalues are $1$, $(1/4)^2$ and $-1/16$

Note the double eigenvalue.  There is only one eigenvector and so the system is geometrically degenerate.  This is what gives rise to the poor behaviour.

The eigencomponents are:-
$$
\left\lceil\matrix{
1\cr1\cr1\cr1\cr\vdots}\right\rceil
\matrix{[1][\matrix{1&0&0&0}]\cr\ \cr \ \cr\ }
\hbox{ , }
\left\lceil\matrix{
0\cr1\cr4\cr9\cr\vdots}\right\rceil
\matrix{[1/4][\matrix{3&-4&1&0}]\cr\ \cr\ \cr \ \cr\ }
\hbox{ and }
\left\lceil\matrix{
0\cr0\cr0\cr1\cr\vdots}\right\rceil
\matrix{[-1/16][\matrix{14&-27&18&-5}]\cr\ \cr \ \cr\ cr\ }
$$

The part of the matrix contributing to the eigensystem for the odd part is
$$\left\lceil\matrix{
10&-1&0\cr
16&0&0\cr
9&9&-1\cr
}\right\rceil/16$$
The eigenvalues are $1/2$, $1/8$ and $-1/16$

The eigencomponents are:-
$$
\left\lceil\matrix{
1\cr2\cr3\cr\vdots}\right\rceil
\matrix{[1/2][\matrix{1&-1/8&0}]\cr\ \cr \ \cr\ }
\hbox{\quad,\qquad}
\left\lceil\matrix{
1\cr8\cr27\cr\vdots}\right\rceil
\matrix{[1/8][\matrix{2&-1&0}]\cr\ \cr \ \cr\ }
\hbox{\quad and\quad}
\left\lceil\matrix{
0\cr0\cr1\cr\vdots}\right\rceil
\matrix{[-1/16][\matrix{5&-4&1}]\cr\ \cr \ \cr\ }
$$



\end

