🚀 go-pugleaf

and ending knots.

Mr Morken was nice to explain the problem, here is the solution.


> It seems there is a solution to that problem as stated in
>
> Making the Oslo Algorithm More Efficient
> T. Lyche, K. Morken
> SIAM Journal of Numerical Analysis Vol 23 No 3 June 1986 pp 663-675
>
> At page 670, there is the following footnote:
>
> "In order to handle the complications near the beginning and end of the knot
> vectors, it is convenient to first extend tau and t to b-infinite sequences,
> apply the results in paragraph 3, and then restrict the range of the indices to
> the original, finite sequences."
>
> I have problems understanding this footnote, and unfortunately nobody in my
> school seems capable to help me.  I am sure you someone in netland can explain
> it or can redirect me on a reference treating the problem.

The point of this is the following:

Since the first and last k knots of your knot vector do not coincide you can
make them do so. What we said in the footnote is what is commonly done in
papers of this type. Here is a more detailed explanation.
Find a real number a and a real number b, such that a is smaller than all
the knots in t and tau, and b is greater than all the knots in t and tau.
Form new knot vectors t' and tau' by inserting k knots at a and b in t and tau.
If you have a curve on the knot vector tau you can write it as a curve
on tau' by inserting k coefficients equal to zero before and after the
coefficients relative to tau. You can then do knot insertion from tau'
to t' with the standard algorithm and then just erase the first and last k
coefficients to get the coefficients relative to t.

The algorithms given in the paper you refer to work for all sorts
of knot vectors including your case. However, there are a few misprints.
Below is a TeX-file with the corrected versions.


Good luck!


Knut Morken
University of Oslo
Norway





\font\csmallc=cmcsc10
\font\stor=cmbx10 scaled \magstep1
%
%Macro for proclaiming things like theorems etc.
%
\def\proclaim#1{%
\medbreak\noindent%
{\csmallc#1.\enspace}
\sl}
%
\def\finishproclaim {\medbreak \rm}
%
\noindent
\line{{\stor ERRATUM}\hfil \rm Date: Sept.~25--1986}
\bigskip
\centerline{\bf Making the Oslo Algorithm more efficient}
\medskip
\centerline{by}
\medskip
\centerline{T.~Lyche and K.~M\o rken}
\medskip
\centerline{in}
\medskip
\centerline{SIAM J.~Num.~Anal., 23 (1986), 663-675.}
\vskip 2.0 true cm
\noindent
The following corrected version of Algorithm~1 p.~671 should be used:

\proclaim{Algorithm 1} Let $j\in\{m_1,\ldots,m_2\}$. Then no
$\alpha_{i,k}(j)$ is nonzero if any of (3.2)--(3.5) hold.
Otherwise, let $\mu$ be such that $\tau_\mu\le t_j<\tau_{\mu+1}$.
By performing the following steps the entries of (3.7)
are computed.
\goodbreak
\newcount\lno
\def\nmb{\number\lno.}
\def\incr{\advance\lno by 1 \relax}
$$\vbox{\rm\incr\+\nmb\quad\cleartabs &$i:=j+1$; $\mu':=\mu$;\cr
\incr\+\nmb&{\bf while} $t(i)=\tau(\mu')$ {\bf and $i<j+k$ do}
($i:=i+1$; $\mu':=\mu'-1$;)\cr
\incr\+\nmb&${\it ih}:=\mu'+1$; $\nu:=0$;\cr
\incr\+\nmb& {\bf for} $p:=1$, 2, \dots, $k-1$\cr
\bgroup\lno=0\incr\+&\nmb\quad&{\bf if $t(j+p)=\tau(ih)$ then} $ih:=ih+1$\cr
\+&&{\bf else} ($\nu:=\nu+1$; $\xi(\nu):=t(j+p)$;)\cr\egroup
\incr\+\nmb& ${\it ah}(k,1):=1$;\cr
\incr\+\nmb&{\bf for} $p:=1$, 2, \dots, $\nu$\cr
\bgroup\lno=0\incr\+&\nmb\quad&${\it \beta 1}:=0$; ${\it tj}:=\xi(p)$;\cr
\incr\+&\nmb& {\bf if $p>\mu'-{\it n1}$ then}\cr
\+&&${\it \beta 1}:=({\it tj}-\tau({\it n1}))*{\it ah}({\it n1}+k-\mu',p)
/(\tau({\it n1}+p+k-\nu-1)-\tau({\it n1}))$;\cr
\incr\+&\nmb& $il:=\max({\it n1}+1,\mu'-p+1)$; $iu:=\min(\mu',{\it n2}+\nu-p)$;\cr
\incr\+&\nmb&{\bf for} $i:=\it il$, ${\it il}+1$, \dots, $\it iu$\cr
\bgroup\lno=0\incr\+&&\nmb\quad&${\it d1}:={\it tj}-\tau(i)$;
${\it d2}:=\tau(i+p+k-\nu-1)-{\it tj}$;\cr
\incr\+&&\nmb& $\beta:={\it ah}(i+k-\mu',p)/({\it d1}+{\it d2})$;\cr
\incr\+&&\nmb&${\it ah}(i+k-\mu'-1,p+1):={\it d2}*\beta+{\it \beta 1}$;\cr
\incr\+&&\nmb& ${\it \beta 1}:={\it d1}*\beta$;\cr\egroup
\incr\+&\nmb& ${\it ah}({\it iu+k-\mu'},p+1):={\it \beta 1}$;\cr
\incr\+&\nmb& {\bf if ${\it iu}<\mu'$ then}\cr
\+&& ${\it ah}({\it iu+k-\mu'},p+1):=$\cleartabs &
${\it \beta 1}+(\tau({\it n2}+k)-{\it tj})
*{\it ah}({\it iu}+k-\mu'+1,p)$\cr
\+&&&$/(\tau({\it n2}+k)-\tau({\it iu}+1))$;\cr
\egroup}$$
\finishproclaim
\medskip
This version differs only in statement~6.2 from the published version
which may give wrong results when ${\it n1} \not = 1$.

\vfill
\break
The following version of Algorithm~2 should be used:
\proclaim{Algorithm 2} Let $j\in\{m_1,m_1+1,\ldots,m_2\}$. If any of
(3.2)--(3.5) hold then $d_j=0$. Otherwise, let
$\mu$ be such that $\tau_\mu\le t_j< \tau_{\mu+1}$. In order to
compute $d_j$, perform the following steps.
\goodbreak
$$\vbox{\rm\lno=0
\incr\+\nmb\quad\cleartabs&$i:=j+1$; $\mu':=\mu$;\cr
\incr\+\nmb&{\bf while $t(i)=\tau(\mu')$ and $i<j+k$ do} ($i:=i+1$; $\mu':=\mu'-1$;)\cr
\incr\+\nmb&${\it ch}(k):=${\bf if $\mu'\le {\it n2}$ then $c(\mu')$ else} 0;\cr
\incr\+\nmb& ${\it ih}:=\mu'+1$; $\nu:=0$;\cr
\incr\+\nmb&{\bf for} $p:=1$, 2, \dots, $k-1$\cr
\bgroup\lno=0\incr\+&\nmb\quad&{\bf if $t(j+p)=\tau({\it ih})$ then}
${\it ih}:={\it ih}+1$\cr
\+&&\bf else begin\cr
\bgroup\lno=0\incr\+&&\nmb\quad&$\nu:=\nu+1$; $\xi(\nu):=t(j+p)$;\cr
\incr\+&&\nmb& ${\it il}:=\max(\mu'-\nu+1,{\it n1})$;
${\it iu}:=\min(\mu',{\it n2}+\nu)$;\cr
\incr\+&&\nmb&$ s:={\it il}-\mu'+\nu-1$; ${\it k\nu}:=k-\nu+s$;\cr
\incr\+&&\nmb&$ch({\it k\nu}):=$&\bf if $\mu'-\nu<{\it n1}$ or $\mu'-\nu>{\it n2}$\cr
\+&&&& {\bf then $0$ else} $c(\mu'-\nu)$;\cr
\incr\+&&\nmb&${\it\tau 2}:=$ {\bf if $\mu'-\nu\le {\it n2}$
then $\tau(\mu'+{\it k\nu})$ else} $\tau({\it n2}+k)$;\cr
\incr\+&&\nmb&{\bf for} $i:={\it il}$, ${\it il}+1$, \dots, $\it iu$\cr
\bgroup\lno=0\incr\+&&&\nmb\cleartabs\quad&$s:=s+1$; ${\it k\nu}:={\it k\nu}+1$;\cr
\incr\+&&&\nmb&${\it d1}:=\xi(s)-\tau(i)$; ${\it d2}:={\it \tau 2}-\xi(s)$;\cr
\incr\+&&&\nmb&${\it ch}({\it k\nu}):=({\it d1*ch(k\nu)}
+{\it d2*ch(k\nu}-1))/({\it d1}+{\it d2})$;\cr\egroup
\egroup\egroup\+&&&\bf end;\cr
\incr\+\nmb& ${\it dj}:={\it ch}(k)$;\cr}$$
\finishproclaim
\medskip
We would also like to point out that $\tau_{i+k-\nu}$ should be replaced
by $\tau_{i+k-\nu-1}$ in Equation~(3.10).
\bye
-- 
-------------------------------------------------------------------------------
Francis Balaguer, DI/LIG Ecole Polytechnique Fed. de Lausanne CH-1015 Lausanne
E-mail : balaguer@ligsg2.epfl.ch, balaguer@elma.epfl.ch
-------------------------------------------------------------------------------