ON G 2
CONTINUOUS SPLINE INTERPOLATION
OF CURVES IN R d
EMIL
ZAGAR
FaultyofComputerandInformationSiene,UniversityofLjubljana,Trzaska25
1000Ljubljana,Slovenia. email: emilgollum.fri.uni-lj.si
Abstrat.
Inthis papertheproblem ofG 2
ontinuousinterpolation ofurvesinR d
by poly-
nomialsplinesof degree n isstudied. Theinterpolation of thedata points,and two
tangent diretions at the boundaryis onsidered. The ase n =r+2=d, where r
is thenumberof interiorpoints interpolated by eah segment of the splineurve, is
studiedindetail. Itisshownthattheproblemisuniquelysolvableasymptotially,i.e.,
whenthedatapointsaresampledregularlyandsuÆientlydense,andlieonaregular,
onvexparametriurveinR d
. Inthis ase theoptimal approximation orderisalso
determined.
AMSsubjetlassiation: 65D05,65D07.
Keywords: Splineurve,G 2
ontinuity,interpolation,approximationorder.
1 Introdution.
TheproblemofparametripolynomialinterpolationofdatapointsinR d
has
alreadybeenstudiedin[1℄{[5℄,[7℄,[9℄and[10℄. Perhaps[1℄ gavetherstimpe-
tustothissubjet. In[9℄,aniegeneralapproahofinreasingtheapproxima-
tionorderbyparametripolynomialinterpolationmethodshasbeendeveloped.
Here,weapplythisgeneralapproahto theG 2
ontinuoussplinease.
The geometri ontinuity is usually hosen in geometri design, sine it refers
toapartiularparametrisation,andassuresthatthegeometriinvariantsofthe
urve, i.e., the tangent diretion, the urvature, et., are ontinuous, but re-
movestheinueneoftheparametrisationontheshapeoftheurve. Ofourse,
itis usually suÆientto requireG 2
ontinuity, sine itis almost impossibleto
reognizethedisontinuitiesofthehigherorderderivativesbythehumaneye.
Theproblem initsgeneralformhasalreadybeenonsideredin[5℄and[7℄,and
anbestatedasfollows. Let
B B BBBBBBB:=BBBBBBBBB
n :[
0
;
m
℄!R d
(1.1)
bethepolynomialsplineurveofdegreenomposedbymsegmentswithbreak-
pointsequene
0
<
1
<:::<
m :
Supposepoints
T T T T T T TT
T
0
;T T T T T T T T
T
1
;:::;T T T T TTTT
T
N 2R
d
; T T T T T T T T
T
j 6=T
T T T T T TT
T
j+1
; j=0;1;:::;N 1;
(1.2)
andtangentdiretions
d d d d d d d d d
0
; ddddddddd
N
; (1.3)
at the boundary points TTTTTTTTT
0 and TTTTTTTTT
N
are given. Find a polynomial spline BBBBBBBBB
denedby(1.1)whihisG 2
ontinuousandinterpolatesgivenpointsandtangent
diretions.
Loally,onthe`-thsegment,BBBBBBBBB anbegivenas
B B B B B B B B
B()=:B B B B B B B B
B
`
` 1
` 1
; 2[
` 1
;
`
℄; `=1;:::;m;
(1.4)
where
` 1 :=
`
` 1
. SineBBBBBBBBBhastointerpolatethedata(1.2)and(1.3),its
`-thpolynomialpieeBBBBBBBBB
`
shouldinterpolaterinteriorandtwoboundarypoints.
Theinterpolatingonditionsonthe`-th segmentnowread
B B B B B B BBB
`
(t
`;j )=TTTTTTTTT
(r+1)(` 1)+j
=:TTTTTTTTT
`;j
; j=0;1;:::;r+1;
(1.5)
where
t
`;0
:=0<t
`;1
<<t
`;r
<t
`;r+1 :=1;
and (t
`;j )
r
j=1
are unknown parametervalues whih have to be determined. It
remainstofulltheGontinuityonditions. TheG 1
ontinuityanbewritten
intheloalparametrisation,i.e., t
` ,0t
`
1,as
d
dt
1 B B B B B B B BB 1
(0) =
0 d d d d d d d d d
0
;
d
dt
`+1 B B B B B B B BB
`+1
(0) =
` d
dt
` B B B B BBBBB
`
(1); `=1;2;:::;m 1;
(1.6)
d
dt
m B B B B BBBBB
m
(1) =
m d d d d ddddd
N
;
andtheG 2
ontinuityrelationsread
d 2
dt 2
`+1 B B BBBBBBB
`+1
(0)= 2
` d
2
dt 2
` B B B B BBBBB
`
(1)+
` d
dt
` B B B B BBBBB
`
(1); `=1;:::;m 1;
(1.7)
where
` and
`
areunknownsand
`
>0. Fig. 1.1showsapartiularpolyno-
mialpieeBBBBBBBBB
`
thatjoinsitsneighbors.
Asalreadyobservedin[5℄,theassumptionthatthenumberofindependentequa-
tionsshould beequaltothenumberofunknownsimpliesthefollowingrelation
dn (d 1)r=3d 2:
(1.8)
Thisleadsto twopratiallyimportantases, n=r+2=dand n=r+1=
2d 1,i.e., theinterpolationbypolynomialsplinesoflowdegree.
B B B B BBBBB
` 1
B B BBBBBB
B
`
B B B B B B BB
B
`+1
Z
Z
Z
Z
Z
Z
~ d
dt
` B B B B B B B B B
`
(0)
d
dt
` B B B B B B B B
B
`
(1) t
d d
t
T T T
T T
T T
TT
` 1;r+1
=TT T
T T
T T
T T
`;0 T T T T T T T T T
`;1
T T T T TTTTT
`;r
T T TTTTTTT
`;r+1
=TTTTTTTTT
`+1;0
Figure1.1: Apartiularsegmentofthesplineurveandsomeoftheimportant
quantities.
The partiular ased =3 was asymptotially(i.e. for thedata sampled on
aregularurvedense enough)solvedin [5℄. Its extensionto generald, butfor
segmentsonly, anbefoundin [7℄. Herewetakletheompositease. Forthe
seondase,i.e.,n=r+1=2d 1,theapproahexplainedherefailsandwill
requiresomeadditionalresearh.
Themainresultofthepaperanbestatedasfollows.
Theorem1.1. IfthedatapointsaresampledregularlyandsuÆientlydense,
thenthereexistsaG 2
polynomialspline urveBBBBBBBBB,whih interpolates given data
pointsandtangentdiretionsatthe boundary. Theapproximation orderisopti-
mal,i.e., r+4=n+2.
The regularityof data pointmentioned in theabove theorem should be ex-
plained. Itislearthatthesolutiondependsonthestrutureofthedataandwe
annotexpetthattheproblemwillbesolvableforthearbitrarysetofpoints.
Sine theasymptoti analysis will be done,the data points will beonsidered
aspointsonasmoothurve. Theywill besampled regularlyin thesense that
thedistributionof pointsaordingto the arlength remainsthe samefor all
segments. And suÆiently dense means that the neighboring pointsare lose
enoughtoeahother.
It is also learthat the approximationorder is optimal sinewehave r+4
interpolation onditions on eah segment (r +2 interpolated points and two
onditionsfortwojoining segmentsonerningG 1
and G 2
ontinuity, i.e., one
onditionforeahsegmentatthebreakpoint).
2 The systemofnonlinear equations for n=r+2=d.
In this setion, the system of nonlinear equations (1.5){(1.7) will be trans-
formedfurtherforthispartiularase. Sinen=r+2,thepolynomialurve
B B B B BBBBB
`
(t):=bbbbbbbbb
`
!
` (t)+
r+1
X
j=0 L
`;j (t)TTTTTTTTT
`;j (2.1)
willsatisfytheinterpolationonditions(1.5)on[
` 1
;
`
℄. Here
!
` (t):=
r+1
Y
j=0 (t t
`;j ); L
`;j (t)=
!
` (t)
(t t
`;j )!_
` (t
`;j )
; !_
` :=
d
dt
`
!
` :
Provided t
`;j
are known, the unknown leadingoeÆient vetorbbbbbbbbb
`
anbe ex-
pressedin twodierentways
b b b b bbbbb
`
= [t
`;0
;t
`;0
;t
`;1
;:::;t
`;r
;t
`;r+1
℄BBBBBBBBB
`
= [t
`;0
;t
`;1
;:::;t
`;r
;t
`;r+1
;t
`;r+1
℄BBBBBBBBB
`
: (2.2)
Sinet
`;0
=0,t
`;r+1
=1,andforasmoothf
[x
0
;x
0
;x
1
;:::;x
i
℄f= i
X
j=0 1
_
!(x
j )
[x
0
;x
j
℄f;
(2.3)
theequation(2.2)anberewrittenas
b b b b b b b b
b
`
= 1
_
!
` (0)
_
B B B B B B B B
B
`
(0)+ r+1
X
j=1 1
_
!
` (t
`;j )t
`;j (T
T T T T T T T
T
`;j T T T T T T TT
T
`;0 )
= 1
_
!
` (1)
_
B B B B B B B BB
`
(1)+ r
X
j=0
1
_
!
` (t
`;j )(t
`;j 1)
(TTTTTTTTT
`;j T T TTTTTTT
`;r+1 ):
(2.4)
Inserting(2.1) into (1.7) and using (2.4), (1.6) in order to replae bbbbbbbbb
` , bbbbbbbbb
`+1 by
_
B B B B B B B B B
`
(1),oneonludesthat
_
B B B B B B B BB
`
(1) =
` 0
2
` 0
r
X
j=0
!
` (1)
_
!
` (t
`;j )(t
`;j 1)
(TTTTTTTTT
`;j T T T T T T T TT
`;r+1 )+
r+1
X
j=0
L
`;j (1)TTTTTTTTT
`;j 1
A
0
r+1
X
j=1
!
`+1 (0)
_
!
`+1 (t
`+1;j )t
`+1;j (TTTTTTTTT
`+1;j T T T T T T T TT
`+1;0 )+
r+1
X
j=0
L
`+1;j (0)TTTTTTTTT
`+1;j 1
A 1
A
: (2.5)
Here
`
=
!
`+1 (0)
_
! (0)
`
!
` (1)
_
! (1)
2
`
`
1
:
Ifwewrite
G G G G G G G G
G
`
0
= r+1
X
j=1
!
`+1 (0)
_
!
`+1 (t
`+1;j )t
`+1;j (T
T T T T T T T
T
`+1;j T T T T T T T T
T
`+1;0 )+
r+1
X
j=0
L
`+1;j (0)T
T T T T T T T
T
`+1;j
;
G G G G G G G G
G
`
1
= r
X
j=0
!
` (1)
_
!
` (t
`;j )(t
`;j 1)
(T T T T T T T T
T
`;j T T T T T T TT
T
`;r+1 )+
r+1
X
j=0
L
`;j (1)T
T T T T T T T
T
`;j
;
and
H H HHHHHHH
`
= r
X
j=0
1
_
!
` (t
`;j )(t
`;j 1)
(TTTTTTTTT
`;j T T TTTTTTT
`;r+1 )
r+1
X
j=1 1
_
!
` (t
`;j )t
`;j (TTTTTTTTT
`;j T T T T T T T TT
`;0 );
thenrelation (1.6)leadsby of (2.4),(2.5) to thefollowingsystemof nonlinear
equations
F F F F F F F F
F
1 :=
1
_
!
1 (1)
( 2
1 G G G G G G G G
G 1
1 G G G G G G GG
G 1
0 )+H
H HHHHHH
H
1
0
_
!
1 (0)
d d d d dddd
d
0
=0 0 0 0 0000
0;
F F F F F F F F F
` :=
`
_
!
` (1)
( 2
` G G G G G G G G G
`
1 G G G G GGGGG
`
0 )+HHHHHHHHH
`
` 1
` 1
_
!
` (0)
( 2
` 1 G G G G G G G G G
` 1
1 G G G G G G GGG
` 1
0
); `=2;3;:::;m 1;
(2.6)
F F FFFFFFF
m :=
m
_
!
m (1)
d d d d d d d dd
N +HHHHHHHHH
m
m 1
m 1
_
!
m (0)
( 2
m 1 G G GGGGGGG
m 1
1
G G G G G G G G G
m 1
0 ):
Notethattheequationsfortherstandforthelastsegmentaredierentsine
d d d d d d d d d
0 and ddddddddd
N
are given. Thus one has md nonlinear equations for md salar
unknowns
(t
`;j )
m;r
`=1;j=1
; (
` )
m
`=0
; (
` )
m 1
`=1 :
Thebestwaytotaklesuhsystemsofnonlinearequationsturnedouttobethe
homotopyontinuationmethods,aswasreportedin [3℄{[5℄.
3 Asymptoti analysis.
Sine the system of nonlinear equations obtained in the previous setion is
diÆult to analyze in full generality, the asymptoti analysis will be applied
here. Under ertainonditionstheexisteneof theuniqueasymptotisolution
ofthesystem(2.6)willbeproved. Thiswillbedoneinthefollowingway. First,
thesolutionatthelimitpointwillbefound. ThentheregularityoftheJaobian
matrixoftheanalyzedsystemat thelimitpointwillbeproven. Sineitisvery
diÆulttodo itin thegeneralase, theregulardistribution ofthedata points
(i.e. the distribution of the parameter values at whih the underlying urve
maththedata inthearlengthparametrisation isequalforallthesegments)
willbe required,whihassures theJaobianbeingthe Toeplitz-likematrix. It
makesiteasiertoanalyze,sineoneanapplythegeneraltheoryofsystemsof
dierene equations. After that the impliit funtion theorem will be used to
establishtheexisteneofthesolutionin theneighborhoodofthelimitsolution.
Suppose thatthedata(1.2)and(1.3)arebaseduponasmoothregularpara-
metriurvefffffffff :[0;L℄!R d
,parametrizedbythear lengthparameter. Obvi-
ously, (2.6)involvesdataand unknownsfrom three onseutivesegmentsonly.
Letusreallthefat,observedin[3℄,thateahblokofequationsanbesimpli-
edbysometranslationandrotation. So fffffffff anbe,withoutloosing generality,
loallyparametrizedbythearlengthparametersas
f f fffffff
`
(s); s2[ h
` 1
;h
` +h
`+1
℄;
(3.1)
withh
` :=Æ
`
handbounded globalmeshratio0<Æ
0 Æ
`
1,where
f f f f f f fff
`
(0)=TTTTTTTTT
`;0 :=000000000;
d
ds f f f f fffff
`
(0)=eeeeeeeee
1 :
Hereeeeeeeeee
i
is theunit vetor,i.e.,
e e e e e e e e e
i
(0):=[0;0;:::;0
| {z }
i 1
;1;0;:::;0
| {z }
d i
℄ T
:
Thedomainofthedenition of thear lengthparametersin(3.1)washosen
toassurethat theoriginof theloaloordinatesystemisinTTTTTTTTT
`;0
at s=0,and
srunsoverthethreeneighboringsegmentsoftheunderlying urvefffffffff whihare
involvedin thepartiularset ofequationswhihhastobeanalyzed.
If the
`
i
, i = 1;2;:::;d 1, are the rst d 1 prinipal urvatures of fffffffff
`
,
expandedloallyas
`
i (s)=
`
i;0 +
1
1!
`
i;1 s+
1
2!
`
i;2 s
2
+:::;
andfffffffff
`
isaregularurvein thesense that
d
ds f f f f f f f ff
`
;:::; d
d 1
ds d 1
f f f f f f fff
`
arelinearlyindependentvetorsinR d
,then
`
i;0
onst>0; i=1;2;:::;d 2:
Additionally, we shall assume that
`
d 1;0
onst > 0. With the aid of the
Frenet-Serretformulaeandtheexpansionoftheprinipalurvatures,oneobtains
theloal expansion
f f fffffff
`
(s) = fffffffff
`
(0)+ d
ds f f f f f f f f f
`
(0)s+ 1
2!
d 2
ds 2
f f f f fffff
`
(0)s 2
+
= fffffffff
`
(0)+(s 1
6 (
`
1;0 )
2
s 3
+)eeeeeeeee
1 (3.2)
+ ( 1
2
`
1;0 s
2
+ 1
6
`
1;1 s
3
+)eeeeeeeee
2 +(
1
6
`
1;0
`
2;0 s
3
+)eeeeeeeee
3 +
Using(3.1),thedatapointsanbewrittenas
T T T T T T TTT
` 1;j
= fffffffff
`
(h
` 1 (
` 1;j 1));
T T TTTTTTT
`;j
= fffffffff
`
(h
`
`;j );
(3.3)
T T T T TTTTT
`+1;j
= fffffffff
`
(h
` +h
`+1
`+1;j );
where
`;0
:= 0 <
`;1
< <
`;r
<
`;r+1
:= 1, ` = 1;2;:::;m, are given
parametervalues. Theexpansion(3.2)andtheequations(3.3)nallygive
T T TTTTTTT
`;j
=
"
h i
Æ i
`
i
`;j 1
i!
i 1
Y
q=1
`
q;0 +O(h
i+1
)
#
d
i=1 : (3.4)
Applyingtheseexpansionstotheequations(2.6)andmultiplyingthembyD 1
` ,
where
D
`
=diag h;
1
2!
h 2
1
Y
q=1
`
q;0
;:::; 1
d!
h d
d 1
Y
q=1
`
q;0
!
;
thenormalizedsystemofnonlinearequationsreads
e
F F FFFFFFF
` :=D
1
` F F F F F F F F F
`
=000000000; `=1;2;:::;m:
(3.5)
Let
e
T T T T T T T T T
` 1;j :=D
1
` T T T T T T TTT
` 1;j
=[Æ i
` 1 (
` 1;j 1)
i
℄ d
i=1
+O(h);
e
T T T T T T T T T
`;j :=D
1
` T T T T T T T T T
`;j
=[Æ i
`
i
`;j
℄ d
i=1
+O(h);
(3.6)
e
T T T T T T T T T
`+1;j :=D
1
` T T T T T T T TT
`+1;j
=[(Æ
` +Æ
`+1
`+1;j )
i
℄ d
i=1
+O(h);
and
e
0 :=
0
h
; e
m :=
m
h :
Thelimitsolutionofthenormalizedsystemisgivenbythefollowinglemma.
Lemma 3.1. As h!0,the solutionof the system(3.5)is
e
0
= Æ
1
`
= Æ
`+1
Æ
`
; `=1;2;:::;m 1
e
m
= Æ
m (3.7)
t
`;j
=
`;j
; `=1;2;:::;m; j=1;2;:::;r:
`
=
Æ
`+1
Æ
`
!
`+1 (0)
_
!
`+1 (0)
Æ 2
`+1
Æ 2
`
!
` (1)
_
!
` (1)
1
; `=1;2;:::;m 1;
where
!
` (t)=
r+1
Y
(t t
`;j ):
Proof. Theproofis rathertehnialandsomedetails willbeomitted. The
limit behaviorof the relation (3.5) as h ! 0 has to be shown. Sine all the
alulationsaresimilar,wewill, e.g.,showhow
lim
h!0 D
1
` G G GGGGGGG
` 1
0
= r+1
X
j=1
!
` (0)
_
!
` (t
`;j )t
`;j lim
h!0 (
e
T T T T T T T T T
`;j e
T T T T TTTTT
`;0 )+
r+1
X
j=0
L
`;j (0)lim
h!0 e
T T TTTTTTT
`;j
; (3.8)
anbesimplied to
2Æ 2
` e e e e e e e e e
2
!
` (0)
_
!
` (0)
Æ
` e e e e eeeee
1 :
Here
L
`;j (t)=
!
` (t)
(t t
`;j )!_
` (t
`;j )
:
Reallthat (3.8)is apart ofthe nonlinearequation e
F F F F F F FF
F
`
=0 0 0 0 0 0 0 0
0 onsidered at the
limitpoint.
Fortherstpartofexpression(3.8),therelation(3.6)andwell-knownproperties
ofthedivideddierenesareused,whihgives
r+1
X
j=1
!
` (0)
_
!
` (t
`;j )t
`;j lim
h!0 (
e
T T T T T T T T T
`;j e
T T T T TTTTT
`;0 )=!
` (0)
r+1
X
j=1 1
_
!
` (t
`;j )
[Æ i
` t
`;j i 1
℄ d
i=1
= !
` (0)[t
`;0
;t
`;1
;:::;t
`;r+1
℄[Æ i
`
i 1
℄ d
i=1
!
` (0)
_
!
` (0)
[Æ i
` t
`;0 i 1
℄ d
i=1
= !
` (0)Æ
d
` e e e e e e e e e
d
!
` (0)
_
!
` (0)
Æ
` e e e e e e e ee
1 :
Fortheseondpartreallalsotheidentities
t q
= r+1
X
j=0 t
`;j q
L
`;j
(t); q=0;1;:::;r+1;
and
t r+2
=!
` (t)+
r+1
X
j=0 t
`;j r+2
L
`;j (t);
whihareapplied toobtain
r+1
X
j=0
e
L
`;j (0) lim
h!0 e
T T T T T T T T
T
`;j
=2Æ 2
` e e e e e e e e
e
2 Æ
d
`
!
` (0)e
e e e e e e e
e
d :
Similarlytheothertermsof (3.5)arehandled and itiseasy toshowthat they
sumto zerowhihompletestheproofofthelemma.
It remains to prove the regularity of the Jaobian of the nonlinear system
(3.5)atthelimitsolution. Tosimplifythealulationofthepartialderivatives,
itis moreonvenientto reverse the roleof the unknownsand the parameters,
as in [9℄. The impliit funtion theorem an then be applied at the end to
ompletetheproof. Soletusassumeforawhilethatttttttttt
`
=(t
`;j )
m;r
`=1;j=1
aregiven
parameters,and
`
=(
`;j )
m;r
`=1;j=1
are theunknowns. Expliit omputationof
theJaobianrequiresapartiularorderingoftheunknowns. Thefollowingone
willbeonsidered:
e
0
;
1
;
1
;
1
;
2
;
2 :::;
m 1
;
m 1
;
m
;e
m :
This ordering and the fat that there are only three neighboring segments in-
volvedinthepartiularsetofequationsofthenonlinearsystem(3.5),implythat
theJaobianisabloktridiagonalmatrix. Butthestudyofitsregularityisstill
verydiÆult,andsomefurtherassumptionsareneeded. Suppose thatthedata
pointsareregularly sampled. Itmeans thatthelengthsof thesegmentsof the
urvefffffffff are allequal,i.e, Æ
`
=1forall `, andthe omponentsof thevetorttttttttt
`
(whihareparametersnow)areequallydistributedoneahsegment,i.e.,
t
j :=t
`;j
; `=1;2;:::;m; j=0;1;:::;r+1:
Thelimitsolutionfromlemma3.1thenbeomes
e
0
=
`
=e
m
=1; `=1;2;:::;m 1;
`;j
= t
j
; `=1;2;:::;m; j=1;2;:::;r;
(3.9)
`
=
=
!(0)
_
!(0)
!(1)
_
!(1)
1
; !(t)= r+1
Y
j=0 (t t
j );
and the Jaobian, say J
m
, is a blok tridiagonal Toeplitz-like matrix. This
propertywill beusedto provetheregularityofJ
m
atleast formlargeenough
whihwill implythetheorem1.1 statedin theintrodution.
Whatfollowsnowisthetehnialpartoftheproofofthetheorem.
Firstthe JaobianJ
m
of thesystem at the limitpointwill be derived. If the
notationa:=!(1)=_ !(0),_ b:=!(1)= !(1),_ :=2
,andu
j
=t
j
=(t
j
1)isused,
theolumnsofJ
m
arisingfromthe`-thsegment(1<`<m)ofthenormalized
system(3.5)andomputedatthelimit(3.9),are
` 1;j e
F F F F FFFF
F
`
=
a
(t
j 1)
2
_
!(t
j )
[i(t
j 1)
i 1
℄ d
i=1
;
` 1 e
F F F F FFFF
F
`
=
2
_
!(0)
[1;0;:::;0℄
T
;
` 1 e
F F F F FFFFF
`
= 1
_
!(0)
[1 b;2;0;:::;0℄
T
;
`;j e
F F F F FFFFF
`
=
1 (u
j +1=u
j )
t
j (t
j
1)!(t_
j )
[it i 1
j
℄ d
i=1
;
e
F F F F FFFFF
`
= 2
!(1)_ [i℄
d
i=1
;
` e
F F F F FFFFF
`
=
_
!(1)
[i(i 1 b)℄ d
i=1
;
`+1;j e
F F F F FFFFF
`
=
at 2
j _
!(t
j )
[i(t
j +1)
i 1
℄ d
i=1 :
Otherunknownsarenotinvolvedin theequationsforthe`-thsegmentandthe
orresponding partial derivatives are zero. Similarly the olumns of the rst
andthelastdiagonalbloksarederived. Multipliationoftheobtainedmatrix
byL=diag(L
1
;L
2
;:::;L
m
),where L
i
=diag (1;1=2;:::;1=d),i =1;2;:::;m,
fromtheleft,andbyR=diag (R
1
;R
2
;:::;R
m ),
R
1
= diag ( !(0);_ vvvvvvvvv T
;!(1)_ =2);
R
j
= diag ( !(0)=;_ v v v v v v v v
v T
;!(1)_ =2); j=2;3;:::;m 1;
R
m
= diag ( !(0)=;_ vvvvvvvvv T
;!(1));_
wherevvvvvvvvv=[t
j (t
j
1)!(t_
j )=℄
r
j=1
,fromtheright,produesthematriesA
1 ,A,
B,C andA
2 ,
A
1
= 2
6
6
6
4
1 (1= u
1 )t
0
1
(1= u
r )t
0
r 1
0 (1= u
1 )t
1
1
(1= u
r )t
1
r 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 (1= u
1 )t
d 1
1
(1= u
r )t
d 1
r 1
3
7
7
7
5
;
A= 2
6
6
6
6
6
4
1= b a
11 a
12
a
1r 1
1 a
21 a
22
a
2r 1
0 a
31 a
32
a
3r 1
.
.
. .
.
. .
.
.
0 a
d1 a
d2
a
dr 1
3
7
7
7
7
7
5
;
wherea
k j
:=(1= u
j 1=u
j )t
k 1
j ,
B= 2
6
6
6
4
b=a (t
1 +1)
0
=(au
1
) (t
r +1)
0
=(au
r ) 0
(1 b)=a (t
1 +1)
1
=(au
1
) (t
r +1)
1
=(au
r ) 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(d 1 b)=a (t
1 +1)
d 1
=(au
1
) (t
r +1)
d 1
=(au
r ) 0
3
7
7
7
5
;
C= 2
6
6
6
4
0 au
1 (t
1 1)
0
au
r (t
r 1)
0
a
0 au
1 (t
1 1)
1
au
r (t
r 1)
1
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 au
1 (t
1 1)
d 1
au
r (t
r 1)
d 1
0 3
7
7
7
5
;
and
A
2
= 2
6
6
6
6
6
4
(1= b) (1= 1=u
1 )t
0
1
(1= 1=u
r )t
0
r 1
1 (1= 1=u
1 )t
1
1
(1= 1=u
r )t
1
r 1
0 (1= 1=u
1 )t
2
1
(1= 1=u
r )t
2
r 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 (1= 1=u
1 )t
d 1
(1= 1=u
r )t
d 1
1 3
7
7
7
7
7
5 :
Notethatallthesematriesarequadratisined=r+2.
ThetransformedJaobian,say e
J
m
, nowbeomes
e
J
m :=LJ
m R=
2
6
6
6
6
6
6
6
6
6
6
6
6
4 A
1
B 0 0 0
C A B 0 0
0 C A
.
.
. .
.
.
0
0 0
.
.
. .
.
. .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
. .
.
.
A B 0
.
.
. .
.
. .
.
. .
.
.
C A B
0 0 0 0 C A
2 3
7
7
7
7
7
7
7
7
7
7
7
7
5 : (3.10)
Observethattherstandthelastdiagonalbloksaredierentfromtheothers,
sinethetangentdiretionsattheboundaryaregiven. Thisiswhytheobtained
matrixisblokToeplitz-likeandnotexatlyblokToeplitz.
Matries L and R are obviously invertible. Consequently, J
m
is invertible if
e
J
m
=LJ
m
Ris. Itwillbeshownthat e
J
m
isinvertibleformlargeenough. The
fatthatthematrixisblokToeplitz-likewillbeused. Inthisasetheproblemof
thenon-singularityof thematrix isloselyonneted withapartiular system
of dierene equations. The solutions of this system depend mainly on the
strutureofthepolynomial
()=det(C+A+ 2
B); 2C;
andthefollowinglemmawillbeprovedrst.
Lemma 3.2. The determinant isexpliitly
()=detV(0;t
1
;:::;t
r
;1)
2 ()
r+1
;
where
2 ()=
1
a
2
+
1
2
+a;
andV(0;t
1
;:::;t
r
;1)isthe Vandermonde matrix.
Proof. Let
P := (C+A+ 2
B)diag(1;t
1 (t
1
1);:::;t
r (t
r
1);1)
= 2
6
6
6
6
6
4
(1= b)+ 2
b=a p
11
p
1r
a
2
(1 b)=a p
21
p
2r
2
(2 b)=a p
31
p
3r
.
.
.
.
.
. .
.
. .
.
. .
.
.
2
(d 1 b)=a p
d1
p
dr
3
7
7
7
7
7
5
;
where
p
k j
:= at 2
j (t
j 1)
k 1
+(t
j (t
j
1)= t 2
j (t
j 1)
2
)t k 1
j +
+
2
(t 1) 2
(t +1) k 1
=a:
Theapproahbasedupon[8℄willbeusednow. Bythedenitionofthedetermi-
nant,detP isapolynomialinvariablest
1
;t
2
;:::;t
r
. Abrieflook attheentries
ofthematrixP revealsthatthetotaldegreeofitsdeterminantisat most
d
X
k =3
(k+1)= r
2
+7r
2 : (3.11)
So,ifallthezerosareguessed,onehastondtheleadingoeÆientonly. Note
that
(p
k j )
d
k =1
t
j
=0
=
a
( a;;:::;) T
;
(p
k j )
d
k =1
t
j
=1
= ( a;;:::;) T
are both proportional to the last olumn of P. Also, only one olumn of P
dependsonxedt
j ,and
t
j (p
k j )
d
k =1
t
j
=0
=
2
a h
2 a
a
2;
a
1;0;1;2;:::;d 3 i
T
;
t
j (p
k j )
d
k =1
t
j
=1
= [2a;a ; 2; 3;:::;( d+1)℄ T
+
1
2
[1;1;:::;1℄
T
;
andagaintherst,the(j+1)-th ,andthelastolumnarelinearlydependent.
Thus detP vanishes twofold at t
j
= 0;1. Sine it vanishes also for t
j
= t
j 0
,
j6=j 0
,
detP =g r
Y
j=1 t
2
j (t
j 1)
2 Y
1j<k r (t
k t
j );
(3.12)
with g possibly depending only on other parameters, but not on t
1
;t
2 :::;t
r ,
sinetherestoftheprodutisalreadyoftotaldegree
4r+
r
2
= r
2
+7r
2
;
whihequals(3.11). Evenmore,gmustequal(forexample)theoeÆientofthe
termt 4
1 t
5
2 t
d+1
r
in detP. Sinethis termis involvedin theonsidered deter-
minantonly twie, namely in p
10 p
2;r+1 Q
r+2
j=3 p
j;j 2 andp
20 p
1;r+1 Q
r+2
j=3 p
j;j 2 ,
aneasyomputationgivesthedesiredoeÆient
g=f( 1) r
((1= b)+ 2
b=a)+( 1) r+1
(
2
(1 b)=a)( a)g
r+2
Y
( 2
=a+(1= 2)+a)=( 1) r
( 2
=a+(1= 2)+a) r+1
:
Theresultofthelemmafollowsafter(3.12)is dividedby Q
r
j=1 t
j (t
j 1).
Sine the roots of will be of partiular interest, the following observation
willbeuseful.
Lemma 3.3. There existonly three distint real roots of ,namely
0
=0,
1 and
2
. Moreover,
1
;
2
6=aandoneoftheroots,say
2
,isdominant,i.e.,
j
1 j<j
2 j.
Proof. Bylemma3.2, therootsof onsists of
0
=0and therootsof
2 .
Sine
2
isquadratipolynomialand(1= 2) 2
4>0(beause<0),
1 and
2
are realand distint. Therelation
1
2
=a 2
>0then impliesthat
1 and
2
havethesamesignandnoneofthemequals a. Consequentlyj
1 j6=j
2 j.
Thesefats willbeusedto provethefollowingtheorem.
Theorem 3.4. If m islargeenough,thenthe matrixJ
m
isnonsingular.
Proof. Itisby(3.10)enoughtoshowthat e
J
m
isnonsingularifmissuÆiently
large. Supposethat thereisxxxxxxxxx2R d
and e
J
m x x x x x x
xxx=000000000. Itwillbeshownthat xxxxxxxxx=000000000
ifmis largeenough. Letusrewritetheequation e
J
m x x x x x x x
xx=000000000intheblokform
e
J
m 2
6
6
6
6
6
4 x x x x x x xx
x
m1
x x xxxxxx
x
m1+1
.
.
.
x x x x x x x x x
m
2
x x x x x x xxx
m
2 +1
3
7
7
7
7
7
5
=0 0 0 0 0 0 0 0
0; x x xxxxxx
x
` 2R
d
; `= m
1
; m
1
+1;:::;m
2 +1;
(3.13)
wherem
1 +m
2
=m 2andm>2. Sine e
J
m
isgivenby(3.10),equation(3.13)
isequivalenttothefollowingsystemofdiereneequations
A
1 x x x x x x x x
x
m1 +Bx
x x x x x x x
x
m1+1
= 0 0 0 0 0 0 00
0
Cxxxxxxxxx
` 1 +Axxxxxxxxx
` +Bxxxxxxxxx
`+1
= 000000000; `= m
1
+1;:::;m
2 (3.14)
Cx x x x x x x x
x
m2 +A
2 x x x x x x xx
x
m2+1
= 0 0 0 0 0 0 00
0:
Inorder to apply the generaltheory of dierene equations ([6℄, p. 181{227),
thesystem(3.14)willbersttransformedtothesystemofdiereneequations
oftherstorder. Let
y y y y yyyyy
`
=
x x x x xxxxx
`
x x x x x x x x x
`+1
; `= m
1
; m
1
+1;:::;m
2 :
Now(3.14)isequivalentto
Myyyyyyyyy
`+1
=Nyyyyyyyyy
`
; `= m
1
; m
1
+1;:::;m
2 1;
(3.15)
where
M=
I 0
0 B
and N =
0 I
C A
;
withI theidentityin R dd
,andtheboundaryonditions
[A
1 B℄yyyyyyyyy
m
1
=000000000;
(3.16)
[C A
2
℄yyyyyyyyy
m
=000000000:
(3.17)
Lemma 3.5. Let():=det(N M). Then has threereal roots,
0
=0,
1 and
2
of multipliity1,r+1andr+1respetively. Thegeneral solutionof
(3.15) is
y y yyyyyyy
m1
= PJ m1
+
0 e e e e eeeee
1
;
y y y y y y yy
y
`
= PJ
`
; `= m
1
+1; m
1
+2;:::;m
2 1;
y y y y y y y y y
m2
= PJ m2
+
1 e e e e e e e ee
2d
;
whereP =[P
1 P
2
℄isthe matrixofgeneralizedeigenvetorsandprinipalvetors
of the matrix penil N M orresponding to
1 and
2
,J =diag(J
1
;J
2 ) is
the orresponding blok Jordan matrix and [
0
; T
;
1
℄ T
2 R 2d
is a vetor of
arbitraryonstants.
Proof. Itiseasytoverifythat
det(N M)=det (C+A+ 2
B)=():
Bylemma3.2, hasthree roots,
0
=0,
1 and
2
ofmultipliity1,r+1and
r+1respetively. Sine thedegreeof is2r+3=2d 1<2d, ithasexatly
onerootatinnity, say
1 .
Tondageneralsolutionof(3.15),onehastoonstruttheanonialformsof
N
i
M,i=0;1;2and
0
N M. Itisthenwellknown([6℄,p. 225{227)that
thegeneralsolutionof (3.15)is
y y y y y y y y y
m
1
= PJ m1
+
0 z z zzzzzzz;
y y y y yyyyy
`
= PJ
`
; `= m
1
+1; m
1
+2;:::;m
2 1;
y y y y y y y y y
m
2
= PJ m2
+
1 w w w w w w www;
whereP =[P
1 P
2
℄isthematrixofgeneralizedeigenvetorsandprinipalvetors
orrespondingto
1 and
2
,J =diag(J
1
;J
2
)istheorrespondingblokJordan
matrix,[
0
; T
;
1
℄ T
2R 2d
is avetorofarbitraryonstants,zzzzzzzzz is ageneralized
eigenvetororrespondingto
0 ,andw
w w w wwww
wisageneralizedeigenvetororrespond-
ingto
1
. SineNz z z z z z z z
z=Mw w w w w w w w
w=0 0 000000
0and therstolumnofC andthelastolumn
ofBarezero,wehavez z z z zzzz
z2Linfe e e e e e e e
e
1 g,w
w wwwwww
w2Linfe e eeeeee
e
2d
g. Consequently,wemyassume
thatzzzzzzzzz=eeeeeeeee
1
andwwwwwwwww=eeeeeeeee
2d .
Sineit isalso knownthat thematrix e
P =[zzzzzzzzzPwwwwwwwww℄ isnonsingular, thesolution
spaeof(3.15)hasdimension2dandtherearenoothersolutions.
Theresultof thetheorem 3.4 willfollowifone anprovethat theboundary
onditions (3.16) and (3.17) imply
0
=
1
= 0 and = 000000000 for m
1
and m
2
suÆientlylarge. Namely,ifthisistrue,thenyyyyyyyyy
`
=000000000,`= m
1
; m
1
+1;:::;m
2 ,
whihimpliesxxxxxxxxx
`
=000000000,`= m
1
; m
1
+1;:::;m
2
+1andker e
J
m
=f000000000g.
It is in fat enough to show that = 000000000. Namely, if = 000000000, then the rst
boundaryondition(3.16)beomes
[A
1 B℄yyyyyyyyy
m
1
=
0 [A
1
B℄zzzzzzzzz=
0 [A
1 B℄eeeeeeeee
1
=000000000:
Sine [A
1 B℄eeeeeeeee
1
is the rst olumn of A
1
, whih is nonzero,
0
must be zero.
Similarly,theseondboundaryonditionreadsas
[CA
2
℄yyyyyyyyy
m
=
1 [CA
2
℄wwwwwwwww=
1 [CA
2
℄eeeeeeeee
2d
=000000000:
Thelast olumnofA
2
islearlynonzero,whihimplies
1
=0.
It remains to prove that is zero. Suppose 6= 000000000. There exists an index i,
1i2d 2,forwhih
i
6=0. Twoaseshavetobeonsidered.
a) Let1id 1. Sinebylemma3.3j
1 j<j
2
j,thedominanteigenvalue
ofJ 1
is1=
1
andthepowermethodassertsthat ifm
1
islargeenough,
1
jjPJ m
1
jj
1 PJ
m
1
= e
u u u u u u u u
u+O(1=m
1 );
where euuuuuuuuu is a generalized eigenvetor orresponding to
1
. Suppose rst
thatj
1
j6=1. Thenormalizedboundaryondition(3.16)implies
[A
1
B℄euuuuuuuuu=000000000:
(3.18)
Weshallshowthatuuuuuuueuumustbezerowhihisanobviousontradition. Sine
e u u u u u u
uuuisageneralizedeigenvetororrespondingto
1
,therelation(N
1 M)euuuuuuuuu
holds,and
(C+
1 A+
2
1 B)uuuuuuuuu
1
=000000000; uuuuuuuuu
2
=
1 u u u u u u u uu
1
; uuueuuuuuu=
u u u u u u u u u
1
u u u u u u u u u
2
: (3.19)
Togetherwith(3.18)onenowonludes
(C+
1 (A A
1 ))u
u u u u u u u
u
1
=0 0 000000
0:
(3.20)
LetusdenethematrixS():=C+(A A
1 ).
Lemma 3.6. The determinantof thematrixS() isexpliitly
detS()=( 1) r
adetV(0;t
1
;t
2
;:::;t
r
;1)( a) r
:
Proof. DeterminantdetS() anbewritten as
det 2
6
6
6
6
6
4
(1= b 1) s
11 s
12
s
1r a
s
21 s
22
s
2r 0
0 s
31 s
32
s
3r 0
.
.
.
.
.
.
.
.
. .
.
. .
.
. .
.
.
0 s
r+2;1 s
r+2;2
s
r+2;r 0
3
7
7
7
7
7
5
;
where
s
k j
=au
j (t
j 1)
k 1
1
u
j t
k 1
j :
Usingsomebasipropertiesofdeterminants,itsimpliesto
detS()=( 1) r
adet [s
k j
℄ r+2;r
k =3;j=1 :
Theremainingdeterminantanbeeasilyomputedbyfollowingtheideas
oftheproofoflemma3.2.
Bylemma 3.3,
1
6=0;a and thedeterminant ofS(
1
)must be nonzero.
Buttherelations(3.20)and(3.19)thenimplyeuuuuuuuuu=000000000whihisaontradi-
tion.
Thesameproofworksin the asewhen j
1
j =1and
1 :=()
d 1
i=1 is not
aneigenvetorofJ 1
1
. Thusitremainstoonsidertheasewhenj
1 j=1
and J 1
1
1
= (1=
1 )
1
. Sine then 0<onst
1
jjPJ k
jj
1
onst
2 ,
forallk,thenormalizedboundaryondition(3.16)beomes
[A
1
B℄euuuuuuuuu+e
0 [A
1
B℄zzzzzzzzz=000000000;
whereuuuuueuuuuisageneralizedeigenvetororrespondingto
1 and
e
0
=
0
=jjPJ m
1
jj
1 :
Thisrelation,(3.19),and thefat that[A
1 B℄z
z zzzzzz
z=e e eeeeee
e
1 imply
(C+
1 (A A
1 ))uuuuuuuuu
1
=
1 e
0 e e e e e e e e e
1 : (3.21)
Thusuuuuuuuuu
1
= (
1
=a)e
0 e e e e e e e e e
d
whihleadseither toeuuuuuuuuu=000000000orontradits(3.20)
andtheproofoftherstaseisomplete.
b) Supposedi2d 2. Thepowermethodnowassuresthat,asm
2 tends
toinnity,
1
jjPJ m
2
jj
1 PJ
m
2
onvergesto ageneralizedeigenvetororrespondingto
2
. The normal-
izedboundaryondition(3.17)beomes
1
jjPJ m
2
jj
1 [C A
2
℄yyyyyyyyy
m2
=[C A
2
℄evvvvvvvvv+e
1 w w w w w w w w
w+O(1=m
2 )=000000000:
Weuseverysimilarargumentsasintherstase. Ifj
2
j6=1,therelation
[C A
2
℄evvvvvvvvv=000000000 (3.22)
musthold. Sinenow(N
2
M)evvvvvvvvv=000000000,wehave
(C+
2 A+
2
2 B)vvvvvvvvv
1
=000000000; vvvvvvvvv
2
=
2 v v v v v v v vv
1
; vvvvvvvvv=
v v vvvvvvv
1
v v vvvvvvv
2
; (3.23)
andtherelation(3.22)imply
(A A
2 +
2 B)v
v v v v v v v
v
1
=0 0 0 0 0 0 0 0
0:
(3.24)
LetT():=A A
2
+B and T
d 1
()denote therstd 1olumnsof
T(). Suppose eeeeeeeeeisavetorofones.
Lemma 3.7. If e
T()=[T
d 1
()eeeeeeeee℄,then
det e
T()=
detV(0;t
1
;t
2
;:::;t
r
;1)
r+1
( a) r
:
Proof. Theproofofthislemmaisalmostthesameastheproofoflemma
3.2andwillbeomitted.
Observe that the last olumn of T() is zero for all , and reall that
2
6=0;a. Theonlusionthat T(
2
)hasrankd 1nowfollowsdiretly
fromthepreviouslemma. ThusT(
2
)hasonedimensionalkernelspanned
byeeeeeeeee
d
. Theonlysolutionsof(3.24)areinLinfeeeeeeeee
d
g,whihleadstovvvvvvvvv
1
=000000000or
v v v v v v vvv
1
=onsteeeeeeeee
d
. Therstsolutionproduesanobviousontraditionevvvvvvvvv=000000000
andtheseondonefails tosatisfy(3.23).
If j
2
j =1,and
2 :=()
2d 2
i=d
is notaneigenvetorof J
2
, theonlusion
(3.24) is still true. Suppose that j
2
j = 1 and J
2
2
=
2
2
. If (3.17)
is normalizedby jjPJ m
2
jj
1
, whih is bounded now, and the relations
(3.23)and[CA
2
℄w w w w wwww
w=e e e e e e e e
eareused, therelation
(A A
2 +
2 B)vvvvvvvvv
1
= e
1
2 e e e e e e e e e;
(3.25)
wheree
1
=
1
=jjPJ m2
jj
1
,is obtained. Sinebylemma3.7 vetoreeeeeeeeeis
notin theimageofT(
2
),(3.25)hasasolutiononlyife
1
=0,i.e.,(3.24)
mustholdandaontraditionfollowsbypreviousonlusions.
Inall ases
=0 0 000000
0, thus
0 and
1
must be zero too. This implies regularity
of e
J
m form
1 andm
2
largeenough(i.e. m largeenough) and theproof of the
theorem3.4isomplete.
Fortheapproximationorderitisenoughtolooktheerroronthe`-thsegment
independently, i.e., dist (BBBBBBBBB
`
;fffffffff). By (1.6) and (2.5) the tangent diretions of
B B B B B B B B B
`
at the boundarypointsare O(h) approximationsof the tangentdiretions
offffffffff, whih is easily obtainedbystraightforwardomputations. Consequently,
thereexistsasmoothurve e
f f f f
fffff withpositiverstd 1prinipalurvatures,whih
interpolatesthegivendatapointsonthe`-thsegmentandthetangentdiretions
ofBBBBBBBBB
`
attheboundarypoints. Additionally,itanbehoseninsuhawaythat
itinterpolatesfffffffff atadditionaltwopointsonthe`-thsegmenttoo. Then
dist(B B B B BBBB
B
`
;f f f f ffff
f)dist (B B B B B B B B
B
`
; e
f f f f f f f f
f)+dist(
e
f f f f ffff
f;f f ffffff
f)=O(h r+4
)+O(h r+4
);
wheretherstpartfollowsfromthesinglesegmentaseanalysisin[7℄,andthe
seondbytheonstrutionof e
f f f f f f ff
f.
Bytheorem3.4theJaobianofthenonlinearsystem(3.5)isnonsingularatthe
limitsolutionfromlemma3.1. Theimpliitfuntiontheoremnowasserts,that
thesystem(3.5)hasasolutionin theneighborhoodof that limitsolution,i.e.,
for h small enough, or equivalently, m large enough. This nally proves the
resultsstatedinthetheorem1.1.
4 Numerial example.
A numerial example will be given here to onrm the results obtained in
theprevioussetions. Sine theresultsforthe urvesin R 3
havealreadybeen
presentedin[5℄weshallonsidertheurveinR 4
.
Lettheurvebegivenby
f f
fffffff :[0;10℄!R 4
: 7!fffffffff():=
0
B
B
os
sin
ln (2+)
ln (1+) 1
C
C
A :
It an be veried that the rst three urvatures of fffffffff are positive on [0;10℄
and the urve satises our requirements. The interpolation points have been
hosen on the urve at the equidistantvalues of the parameter . It is not a
regularsamplinginthesenseofthetheorem1.1butwestillgotasolutionofthe
problem. This indiates that theregularityofdata pointsould be omittedin
thetheorem. Thisfathasbeenonrmedbyotherexamplestoo. Thedetailed
numerialalgorithmforsolvingtheobtainednonlinearsystemtogetherwiththe
numerialresultswillappearelsewhere.
2 4 6 8 10
5e - 5 1e - 4 1.5e - 4 2e - 4 2.5e - 4
Figure4.1: Theestimated parametrierrorfortheurvefffffffff andm=6.
Table4.1: Theresultsfortheurvefffffffff.
m Error Rate m Error Rate
6 2:9010 4
16 1:3810 6
5:67
8 6:3210 5
5:30 18 7:0710 7
5:70
10 1:8910 5
5:41 20 3:8710 7
5:71
12 6:9110 6
5:51 22 2:2410 7
5:73
14 2:9210 6
5:58 24 1:3610 7
5:75
Theparametridistane(i.e. theerror)betweenfffffffff andBBBBBBBBBwasobtainedbythe
methoddesribedin [2℄andalreadyusedin[3℄. Theresultsoftheinterpolation
are shown in Tab. 4.1. The rst olumn is the number of segments of the
spline urve,the seondone theestimatederror, andthe third onetherateof
onvergeneobtainedfromtwoonseutivem. Sineinthisaser=d 2=2,
theapproximationordershouldber+4=6,whihisobviouslyonrmedbythe
resultsinthetable. Fig. 4.1showstheestimatedparametrierrorform=6. It
anbelearlyseenthat fourpointsareinterpolatedoneahsegmentimplying
theerrorbeingzerothere.
REFERENCES
1. C.deBoor,K.Hollig, andM.Sabin,Highauray geometri Hermiteinterpola-
tion,Comput.AidedGeom.Design,4(1987),pp.269{278.
2. W. L. F. Degen, Best approximations of parametri urves by splines, inMath-
ematial Methods in Computer AidedGeometri DesignII, T.Lyhe and L. L.
Shumaker(eds.),AademiPress,1992,pp.171{184.
3. Y. Y. Feng and J.Kozak, On G 2
ontinuous ubi spline interpolation, BIT, 37
(1997),pp.312{332.
4. Y. Y. Feng and J. Kozak, On G 2
ontinuous interpolatory omposite quadrati
Beziere urves,J.Comput.Appl.Math.,72(1996),pp.141{159.
5. Y. Y.FengandJ.Kozak,On splineinterpolation of spae data, inMathematial
Methods forCurvesand SurfaesII,M. Dhlen,T.Lyhe,and L.L. Shumaker
(eds.),VanderbiltUniversityPress, 1998,pp.167{174.
6. I. Gohberg, P.Lanaster, andL. Rodman,Matrix Polynomials,Aademi Press,
1982.
7. J.KozakandE.
Zagar,OnurveinterpolationinR d
,inCurveandSurfaeFitting,
A.Cohen,C.Rabut,andL.L.Shumaker(eds.),VanderbiltUniversityPress,2000,
pp.263{273.
8. C.Krattenthaler,Advaneddeterminantalulus,Sem.Lothar.Combin.,42(1999),
67pp.
9. K.Mrkenand K.Sherer,Ageneralframework forhigh-auray parametri in-
terpolation,Math.Comp.,66(1997),pp.237{260.
10. R. Shabak, Interpolation inR 2
bypieewisequadratis visuallyC 2
Bezier poly-
nomials,Comput.AidedGeom.Design,6(1989),pp.219{233.
