Linear dependence of bivariate Minimal Support and Locally Refined B-splines over LR-meshes

Contents lists available atScienceDirect

Computer Aided Geometric Design

www.elsevier.com/locate/cagd

Linear dependence of bivariate Minimal Support and Locally Refined B-splines over LR-meshes ^{✩ , ✩✩}

Francesco Patrizi

^a

^,

^b

^,∗ , Tor Dokken

^a

aDepartmentofAppliedMathematicsandCybernetics,SINTEF,Forskningsveien1,0373Oslo,Norway bDepartmentofMathematics,UniversityofOslo,MoltkeMoesvei35,0851Oslo,Norway

a r t i c l e i n f o a b s t r a c t

Articlehistory:

Received13November2018

Receivedinrevisedform23October2019 Accepted24October2019

Availableonline13December2019

Keywords:

LRB-splines Localrefinements Lineardependence Minimalsupport

The focusonlocallyrefined splinespaces hasgrownrapidlyinrecent yearsduetothe needinIsogeometricAnalysis(IgA)ofsplinespaceswithlocaladaptivity:apropertynot offered bythe strictregular structure of tensor product B-spline spaces. However, this flexibility sometimes resultsin collections ofB-splinesspanning the spacethat are not linearly independent.InthispaperweaddresstheminimalnumberofMinimalSupport B-splines(MSB-splines)and ofLocallyRefinedB-splines(LRB-splines)thatcan forma lineardependencerelation.WeshowthatsuchminimalnumbersaresixforMSB-splines andeightforLRB-splines.Furtherresultsareestablishedtohelpdetectingcollectionsof B-splinesthatarelinearlyindependent.

©^{2019TheAuthor(s).PublishedbyElsevierB.V.Thisisanopenaccessarticleunderthe} CCBYlicense(http://creativecommons.org/licenses/by/4.0/).

1. Introduction

In 2005 Thomas J.R. Hughes et al.(2005) proposed to reconstitute finite element analysis (FEA) within the geomet- ric framework ofCADtechnologies. Thisgave riseto Isogeometric Analysis (IgA).It unifiesthe fieldsofCAD andFEAby extendingtheisoparametric conceptofthestandard finiteelements toother shapefunctions, suchasB-splinesandnon- uniformrationalB-splines(NURBS),used inCAD.Thisdoesnot onlyallow foranaccurate geometricaldescription,butit alsoimprovessmoothnessproperties.Asaconsequence,IgAmethodsoftenreacharequiredaccuracyusingamuchsmaller numberofdegreesoffreedom (Großmannetal.,2012). Moreover,insome situations,the increasedsmoothnessalso im- proves the stability ofthe approximations resulting infewer nonphysicaloscillations (Hughes et al., 2005; Manni et al., 2011).

However,innumericalsimulations,local(adaptive)refinementsarefrequentlyusedforbalancingaccuracyandcompu- tationalcosts.TraditionalB-splinesandNURBSspacesareformulated astensorproductsofunivariateB-splinespaces.This means that refininginone of theunivariate B-spline spaceswill causethe insertion ofan entirenewroworcolumn of knotsin thebivariatesplinespace, resultingina globalrefinement.In ordertobreakthetensorproduct structureofthe underlyingmesh,newformulationsofmultivariateB-splineshavebeenintroducedaddressinglocalrefineability.

✩ Editor:B.Juettler.

✩✩ ThisworkhasreceivedfundingfromtheEuropeanUnion’sHorizon2020researchandinnovationprogrammeundergrantagreementNo. 675789.

*

Correspondingauthorat:DepartmentofAppliedMathematicsandCybernetics,SINTEF,Forskningsveien1,0373Oslo,Norway.

E-mailaddresses:[email protected](F. Patrizi),[email protected](T. Dokken).

https://doi.org/10.1016/j.cagd.2019.101803

0167-8396/©^{2019TheAuthor(s).PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense} (http://creativecommons.org/licenses/by/4.0/).

1.1. Overviewoflocallyrefinedsplinemethods

The firstlocalrefinementmethodintroducedwere theHierarchicalB-splines, orHB-splines(ForseyandBartels,1988), whosepropertieswerefurtheranalyzedinKraft(1997).TheHB-splinesarelinearlyindependentandnon-negative.However, partition ofunity, which is necessaryfor the convexhullproperty (essential forinterpreting the B-spline coefficientsas controlpoints),wasstillmissing.Torectifythis,TruncatedHierarchicalB-splines,orTHB-splines,wereproposedinGiannelli etal.(2012) and furtheranalyzed inGiannellietal.(2014).InGiannellietal.(2014) they show howtheconstruction of HB-splinescanbemodifiedwhilepreservingthepropertiesofHB-splines,gainingthepartitionofunityandsmallersupport ofthebasisfunctions.

Adifferentapproach,forlocalrefinement,wasintroducedinSederbergetal.(2003) withtheT-splines.Thesearedefined over T-meshes,whereT-junctionsbetweenaxisalignedsegmentsare allowed.T-splines havebeenusedefficientlyinCAD applications, beingableto produce watertightandlocally refinedmodels. However, theuse ofthe mostgeneralT-spline concept inIgA is limited by the risk of lineardependence ofthe resulting splines (Buffa et al., 2010). It is desirable in numericalsimulations touselinearlyindependentbasisfunctionstoensurethattheresultingmassandstiffness matrices havefullrankandavoidthealgorithmiccomplexity posedbysingularmatrices. Analysis-SuitableT-splines,orAST-splines, were thereforeintroduced inda Veigaetal.(2012).As T-splines,AST-splines providewatertightmodels,obey theconvex hullproperty,andmoreoverarelinearlyindependent.

There are many other definitions of B-splines over meshes withlocal refinements, such as PHT-splines (Deng et al., 2008),PB-splines (EngleitnerandJüttler,2017)andLRB-splines(Dokken etal.,2013). Adiscussion ofthedifferencesand similaritiesofHB-splines,THB-splines,T-splines,AST-splinesandLRB-splinescanbefoundinDokkenetal.(2018).

1.2. LRB-splinesandMSB-splines

In this paper we look at Locally Refined B-splines, or LR B-splines, introduced in Dokken et al. (2013). The idea is to extendthe knotinsertion refinement ofunivariate B-splinesto insertion oflocalline segments intensormeshes. The processstartsbyconsideringthetensorproductB-splinespaceoveracoarsetensormesh.Then,whenanewinsertedlocal linesegmentdividesthesupportofoneormoreLRB-splinesintwoparts,weperformknotinsertiontosplitsuchB-splines into two(or more)newones. Thefinal collectionoffunctionsdoesnotsumtoone ingeneral. However, itispossibleto scalethembymeansofpositiveweightssothattheyformapartitionofunity;seeDokkenetal.(2013,Section7).

The LR B-splines area subset of theMinimal SupportB-splines, or MS B-splines. As one canguess fromtheir name, MS B-splinesarethetensorproductB-splineswithminimalsupport,i.e.,withoutsuperfluouslinesegmentscrossingtheir support,identifiableonthelocallyrefinedmesh.ThemaindifferencebetweenLRandMSB-splinesisthattheformerones aredefinedalgorithmically,whilethelatteraredefinedbythetopologyofthemesh.

1.3. Contentofthepaper

The freedom inthe refinement process canresultin undesirable collectionsof LR B-splines. Namely,the LR B-splines obtained atthe endof the refinement process maybe linearly dependent.Assumptions on the refinement process have to be established in order to ensure linear independence. We start such analysis by looking at conditions on the mesh necessaryforlineardependence.Wesaythatfunctions

φ

1

, . . . , φ

n

:

R^d

→

RareactivelylinearlydependentonR^d ifthere exist

α

i

∈

R,

α

i

=

^{0 foralli}

=

¹

, . . . ,

n,suchthat

n

i=¹

α

_i

φ

_i

(

xxx

) =

⁰

, ∀

^xxx

∈ R

^d

.

Notethatweconsequentiallylookattheminimalsetoflinearlydependentfunctionsbyforbiddingzerocoefficientsinthe linearcombination.

Inthisworkweshowthat:

•

^{For anybidegree ppp,the minimal number ofactive MS B-splines ina linear dependencerelation issix, while forLR} B-splinesitiseight.

•

^{Thesenumbers aresharpforanybidegree ppp}

= (

p1

,

p2

)

fortheMS B-splinesandwithp_k

≥

^2,forsomek

∈ {

¹

,

2

}

^,for theLRB-splines.

We lookattheminimalconfigurationsoflineardependencebecauseweconjecturethatanylineardependencerelationis a refinementofoneoftheseminimal cases.Inother words,they aretherootsforthelineardependence.Inparticular,if this istrue,by avoidingthe minimalcases,the MS B-splinesandLR B-splinesarealways linearlyindependent andform a basis. Furthermore, toget such lower bounds, we prove results that can be usedto understand ifthe setof B-splines considered islinearlyindependentornot.Inparticular,theycanbe usedtoimprovethePeelingAlgorithm(Dokkenetal., 2013,Algorithm6.3)toverifyiftheLRB-splinesdefinedonagivenmesharelinearlyindependent.

Fig. 1.Example of box–partition and corresponding mesh.

1.4. Structureofthepaper

InSection2weprovideanintroductiontotheconceptsofbox-partitions,meshesandLR-meshes.InSection3wedefine theunivariatesplinespaceoveraknotvectorsequenceandthebivariatesplinespaceoverabox–partitionandwerecallthe dimensionformulapresentedinPettersen(2013).Thenwediscussconditionsonthemeshforensuringthatthedimension formuladependsonly on thetopology of themesh. InSection 4 we recall univariate andbivariateB-splines, their basic propertiesandtheknot insertionprocedure. InSection 5we definethe MS B-splinesandthe LRB-splinesandwe show whenthesetwosetsaredifferent.InSection6westudythespanningpropertiesoftheLRandMS B-splines.Inparticular westatenecessaryandsufficientconditionsforspanningthefullsplinespace.Knowingthedimensionofthesplinespace, we cancheck lineardependenciesjustby countingtheelements intheLR, orMS, B-splineset.In Section 7,we identify necessaryfeatures fora lineardependencerelationandwederive theminimal numberofactive MS B-splinesneededin alineardependencerelation.InSection8,wecomputetheminimalnumberofactiveLR B-splinesinalineardependence relation.InSection9werecallbrieflythePeelingAlgorithmforcheckinglinearindependenceandweshowhowtoimprove itbyusingtheresultsofSection7.Finally,wesummarizethemainresultsanddiscussfutureworkinSection10.

2. Box–partitionsandLR–meshes

Thepurposeofthissectionistodescribebox–partitionsin2DanddefinebivariateLR–meshes.Forourscope,andsake ofsimplicity,we decidedtorestrict generaldefinitions,validinanydimension,tothe 2Dcase;we refertoDokken etal.

(2013) forthegeneraltheory.

Definition2.1.Givenanaxis-alignedrectangle

⊆

R²,abox-partitionof

isafinitecollectionE ^ofaxis-alignedrectan- glesin

,calledelements,suchthat:

1. ˚

β

1

∩ β

^˚2

=

∅^forany

β

1

, β

2

∈

E^,with

β

1

= β

2. 2.

β∈E

β =

.

Definition2.2.Givenabox–partitionE^{,wedefinetheverticesof}E ^{astheverticesofitselements.In}particular,avertexof E iscalledT-vertexifitistheintersectionofthreeelementsedges.WedenoteasVthesetofverticesofE.

Definition2.3.Givenabox–partitionE ofarectangle

∈

R²,ameshlineofE isasegmentcontainedinanelementedge, connectingtwoandonlytwoverticesofV^atitsend–points.Thecollectionofallthemeshlinesofthebox-partitioniscalled mesh,M^.GivenameshM^{,onecandefinea}multiplicityfunction

μ :

M

→

N^∗thatassociatesapositiveintegertoevery meshline, calledmultiplicityofthemeshline.Ameshthat hasan assignedmultiplicity function

μ

iscalled

μ μ μ

-extended mesh.

When the T-vertices of E ^{occur only on}

∂

andevery colinear meshlines have samemultiplicity, the corresponding

μ

-extendedmeshiscalledtensormesh.

Finally,ifeverymeshlineofa box-partitionE ^hasthesamemultiplicity m wesay thatthecorresponding

μ

-extended meshhasmultiplicitym.

In thiswork we only consider

μ

-extended meshes. Therefore, we will only write meshes for

μ

-extended meshesto simplifythenotation.

Fig.1showsanexampleofbox-partitionandassociatedmesh:in(a)thebox–partition E ^andin(b)thecorresponding meshM^{.Themeshlinesareidentifiedbysquaresreportingtheassociated}multiplicities.

Ameshlinecanbe expressedasthe Cartesianproductofapoint inR andafiniteinterval.Let

α ∈

Rbe thevalue of such a pointandlet k

∈ {

¹

,

2

}

^{be its positionin theCartesian product.Ifk}

=

^{1 themeshlineis verticalandifk}

=

^{2 the} meshline ishorizontal. We sometimes write k-meshlineto specify the directionof the meshline and

(

k

, α )

-meshlineto specifyexactlyonwhataxis-parallellineinR² themeshlinelies.

Fig. 2.Example of computation of vertical and horizontal multiplicities.

Definition2.4.Givena box-partition E ^andan axis-aligned segment

γ

,we saythat

γ

traverses

β ∈

E ^if

γ _⊆ β

andthe interiorof

β

isdividedintotwopartsby

γ

,i.e.,

β \ γ

isnotconnected.Asplitisafiniteunionofcontiguousandcolinear axis-alignedsegments

γ = ∪

i

γ

isuchthatevery

γ

i eitherisameshlineofthebox-partitionor

γ

i traversessome

β ∈

E^.

Asformeshlines,wesometimeswritek-splitwithk

∈ {

¹

,

2

}

^{tospecifythedirectionofthesplitor}

(

k

, α )

-splittospecify onwhataxis-parallellineinR² thesplitlies,thatis,tospecifythatitliesontheline

{(

^x1

,

x₂

) :

^xk

= α }

^.

Definition2.5.AmeshM^{hasconstantsplitsifanysplit}

γ

inM^{ismadeofmeshlinesofthesame}multiplicity.

When asplit

γ

isinsertedinabox–partitionE^{,anytraversed}

β ∈

E ^{isreplacedby thetwo}subrectangles

β

1

, β

2 given by theclosuresoftheconnectedcomponentsof

β \ γ

.Theresultingnewbox-partitionisindicatedasE

+ γ

anditscorre- sponding meshasM

+ γ

.Assigneda positiveinteger

μ

γ to

γ

,themultiplicitiesofthemeshlines inM

∩ (

M

+ γ )

not containedin

γ

areunchanged,whilethemultiplicitiesofthosethatarein

γ

areincreasedby

μ

γ.Thenewmeshlinescon- tainedin

(M + γ )\M

^havemultiplicityequalto

μ

γ.If

μ

wasthemultiplicityfunctionassociatedtoM^,themultiplicity function onthe refinedmeshM

+ γ

isdenotedas

μ + μ

γ.Themeshesusedin applicationsareoftenresultofa mesh refinementprocess,thatis,givenaninitialcoarsetensormeshM1andasequenceofsplits

γ

iwithassociatedintegers

μ

γi

for i

=

¹

, . . . ,

N

−

^{1,themeshesconsidered are thefinal elementof asequence ofmeshesoftheform}Mi+¹

=

Mi

+ γ

i wheretheassociatedmultiplicityare

μ

i+¹

= μ

i

+ μ

γi.TheLR–meshesareaparticularsubclassofthiskindofmeshes.

Definition2.6.AnLR-meshisameshM^{obtainedthroughasequenceofsplit}insertions:

M1is a tensor mesh

,

Mi+¹

=

Mi

+ γ

ihas constant splits, fori

=

1

, . . . ,

N

−

1 andM

=

MN,forsome N.

In theremainingofthissectionwe introducetheknotvector onasplit andthelength ofit.Theseconceptswillhelp usto analyzethespanning propertiesof theLR B-splinesandtheincrease inthespline spacedimension duetoa mesh refinement.

Definition2.7.GivenameshMcorrespondingtoabox-partitionE^{,foranyvertexvvvin}V^wedefine

μ

1

(

vvv

) =

^max

{ μ ( γ ) :

^vvv

∈ γ

and

γ

1-meshline ofM

}

μ

2

(

vvv

) =

^max

{ μ ( γ ) :

^vvv

∈ γ

and

γ

2-meshline ofM

}

μ

1

(

vvv

)

iscalledverticalmultiplicityand

μ

2

(

vvv

)

horizontalmultiplicityofvertexvvv.

In Fig. 2 is reported an example of computation of horizontal and vertical multiplicities for two vertices of a box–

partition. The meshlines on the left- and right-hand side of vvv1 have multiplicity 1 and 2 respectively. So

μ

2

(

vvv1

) =

max

{

¹

,

2

} =

^{2. The meshlinesabove andbelow vvv}1 haveboth multiplicity 1, sothat

μ

1

(

vvv₁

) =

^{1.Concerning vvv}2,we have

μ

2

(

vvv₂

) =

^2,whereas

μ

1

(

vvv₂

) =

^max

{

¹

} =

^{1 becausethereisnomeshlinebelowvvv}2.

Definition2.8.Given a

(

k

, α )

-split

γ

ina mesh M^{, all thevertices where}

γ

intersects themeshlines ofM^,orthogonal toit,havekth-coordinateequalto

α

anddifferent

(

3

−

^k

)

thcoordinate.Wedefine theknotvectoron

γ

astheincreasing sequence

τττ ⊆

Rgivenbysuch

(

3

−

^k

)

thcoordinates.Theelementsofsuchsequencearecalledknots.Wefurtherdefinethe multiplicity functionoftheknotvectorasthe

μ

3−^k multiplicityfunctionofthecorresponding vertices.Wesaythat

τττ

has lengthdifthemultiplicitiesofitsknotssumtod.

3. Splinespaces

Inthissectionwedefinetheunivariatesplinespaceoveraknotvectorandthebivariatesplinespaceoverabox-partition.

Inparticularweprovidethedimensionformulaofsuchspaces.Forthebivariatespace,theformula,introducedinPettersen (2013),presentstermsdependingonthesizeofthebox–partitionelements.Thismeansthatthedimensionisunstable,i.e., splinespacesonmesheswiththesametopologymighthaveadifferentdimension.Therefore,werecallsufficientconditions foravoidingsuchterms,makingtheformuladependentonlyonthemeshtopology.

3.1. Splinespaceonaknotvectorsequence

Definition3.1.Givenan increasingsequence

τττ = ( τ

1

, . . . , τ

n

)

ofrealnumbers,apositiveinteger panda function

μ : τττ →

N^∗suchthat0

≤ μ ( τ

i

) ≤

^p

+

^{1 foralli,wedefinethe}correspondingsplineknotvectorasthetriple

τττ

^μp

= ( τττ , μ ,

p

)

.

Givenasplineknotvector

τττ

^μp,wesaythat

τ

i

∈ τττ

hasfullmultiplicityif

μ ( τ

i

) =

^p

+

^{1 andwesaythat}

τττ

^μp isopenif

τ

1 and

τ

n havefullmultiplicity.

Sometimesitismoreconvenienttowrite asplineknotvector,intheequivalentway,asthecouplettt_p

= (

ttt

,

p

)

wherettt isanon–decreasingsequencettt

= (

t1

, . . . ,

t

)

,i.e., withti

≤

^ti+¹,where

=

n

i=¹

μ ( τ

i

)

and t1

= . . . =

t_μ(τ1)

=τ1

<

t_μ(τ1)+¹

= . . . =

t_μ(τ1)+μ(τ2)

=τ2

< . . .

WeuseboldGreekletterswiththemultiplicityfunctioninsuperscriptinthefirstwayofexpressionandboldLatinletters forthesecondway.

Givenadegreep,wedenoteas

p

⊂

R

[

^t

]

^{thevectorspacespannedbythemonomialstj suchthat0}

≤

^j

≤

^p.

Definition3.2.Givenasplineknotvector

τττ

^μp

= ( τττ , μ ,

p

)

with

τττ ₌ ( τ

1

, . . . , τ

n

)

,wedefinetheunivariatesplinespaceonthe splineknotvector

τττ

^μp,denotedS(

τττ

^μp

)

,orequivalentlyS(ttt_p

)

,asthesetofallfunctions f

:

R

→

Rsuchthat

1. f iszerooutside

[ τ

1

, τ

n

]

^,

2. therestrictionsof f totheintervals

[ τ

i

, τ

i+¹

)

fori

<

n

−

^{1 and}

[ τ

n−¹

, τ

n

]

^arepolynomialsin

p, 3. f isC^p−μ(τi)-continuousat

τ

i.

Thefollowingisthedimensionofthesplinespaceoveraknotvector.Itisawell-knownresult,proved,e.g.,inSchumaker (2007).

Theorem3.3.Givenasplineknotvector

τττ

^μp

= ( τττ , μ ,

p

)

with

τττ = ( τ

1

, . . . , τ

n

)

,thecorrespondingsplinespaceS(

τττ

^μp

)

hasdimension

dim

S( τττ

^μ_p

) =

^max

n

i=¹

μ ( τ

i

) − (

p

+

¹

),

0

.

(1)

Therefore,ifttt_p hascardinality p

+

^r

+

^{1 for somer}

≥

^{1,then dim}S(ttt_p

) =

^{r.Thereare manypossiblebasesfor}S(ttt_p

)

. Onepossibilityisprovidedbyaclassicalresultinsplinetheory,calledCurry-SchoenbergTheorem(de Boor,1978,Theorem 44).Itensures thatthe socalledB-spline functionsofdegree p,definedontheknotvectortttp,canbeusedasapossible basis:

S(

ttt_p

) =

^span

{

^B

[

^tttip

]}

^r_i=1 ^withtttip

= (

t_i

, . . . ,

t_i+p+1

) ⊆

^tttp

.

ForabriefintroductiontoB-splineswerefertoSection4.

3.2. Splinespaceonabox–partition

Definition3.4.Asplinemesh inR² isatriple N

= (

M

, μ ,

ppp

)

whereM^{isa meshfroma} box–partition E^{, ppp}

= (

p1

,

p2

)

isapairofpositiveintegersand

μ :

M

→

N^∗ isamultiplicityfunctionsuchthat1

≤ μ ( γ ) ≤

^pk

+

^{1 foreveryk-meshline}

γ ∈

M^.Inparticular,ifak-meshline

γ

hasmultiplicity p_k

+

^{1 wesaythat}

γ

hasfullmultiplicity anda splinemeshN isopenifeveryboundarymeshlinehasfullmultiplicity.Aspline meshN ^whereM^{isanLR-meshwillbe calledspline} LR-mesh.

Remark3.5.Givenaspline meshN

= (M, μ ,

ppp

)

,onecan definea splineknotvectoron anyk-splitofM^,fork

∈ {

¹

,

2

}

^: thesequence

τττ

andthemultiplicityfunction

μ

3−karedescribedinDefinition2.8andthedegreeis p_3−k.

Givenabidegreeppp

= (

p1

,

p2

)

,wedenoteas

ppp

⊂

R

[

^x

,

y

]

^{thevectorspacespannedbythemonomialsxi1yi2 suchthat} 0

≤

ⁱk

≤

^pkfork

=

¹

,

2.

Definition3.6.GivenasplinemeshN

= (

M

, μ ,

ppp

)

correspondingtoabox–partitionE ^ofarectangle

= [

^a1

,

b1

] × [

^a2

,

b2

]

^, foranyelement

β ∈

E^,

β =

^J1

×

^J2 with Jk

= [

^aβ,k

,

b_β,k

]

^,weset

β ˜ = ˜

^J1

× ˜

^J2with

˜

J_k

= [

^aβ,k

,

b_β,k

)

ifb_β,k

<

b_k

[

^aβ,k

,

b_β,k

]

^ifbβ,k

=

^bk

.

⁽²⁾

ThesplinespaceonN^,denotedbyS(N

)

,isthesetofallfunctions f

:

R²

→

Rsuchthat 1. f iszerooutside

,

2. foreachelement

β ∈

E,therestrictionof f to

β ˜

isabivariatepolynomialfunctionin

ppp, 3. foreachk-meshline

γ ∈

M^{, f isCpk−μ(γ)}-continuousacross

γ

.

The generaldimensionformulaofthesplinespaceoverspline meshesispresented inPettersen(2013) and hasterms depending onthesizeofthebox–partitionelements.Thismakesthedimensionofthesplinespaceunstable(LiandChen, 2011),i.e.,notonlydependentonthemeshtopology.However,ifweconsiderthesplinespaceoverasplineLR-meshbuilt sothat

LR-rule 1 the starting tensor mesh M1 has at least p1

+

^{2 vertical splits and p}2

+

2 horizontal splits counting their multiplicities,

LR-rule 2 fork

∈ {

¹

,

2

}

^{,theknotvectoronanymaximalk-splithaslengthatleastp}3−^k

+

^{2 atanystepinthe}construction oftheLR-mesh,

then, one can prove,by using the results inPettersen (2013), that, called M^k theset of all the k-meshlines in M, for k

∈ {

¹

,

2

}

^,and

|E|

^thecardinalityofE^,wehave

dim

S(

N

) =

vvv∈V

[ (

p₁

− μ

₁

(

vvv

) +

¹

)(

p₂

− μ

₂

(

vvv

) +

¹

) ]

− (

p₂

+

¹

)

β∈M¹

[ (

p₁

− μ (β) +

¹

) ] − (

p₁

+

¹

)

β∈M²

[ (

p₂

− μ (β) +

¹

) ] + |

E

|(

^p1

+

¹

)(

p₂

+

¹

),

(3)

which dependsonlyon thetopology ofthemesh.In thispaperwewill always assumethe LR-rulesforconstructing LR- meshes.

Remark3.7.IntheLR-meshbuildingprocess,anyextensionofanoldersplitisallowedbeingLR-rule2satisfiedonthenew mesh.

Fromequation(3),itispossibletoprovethedimensionincreasingformula(Dokkenetal.,2013,Theorem5.5).Knowing dimS(N

)

, through this formula, one can easily compute the dimension of the spline space on a refined spline mesh N

+ γ _:= (M + γ , μ ₊ μ

_γ

,

ppp

)

.First,weneedtointroducetheconceptofexpandedsplineknotvectoronasplit.

Definition3.8.WhenasplinemeshN

= (M, μ ,

ppp

)

isrefinedbyinsertingak-split

γ

,sinceitisasplitinM

+ γ

,

γ

has asplineknotvectoronit,

τττ

^μp3^3−k−k,withassignedmultiplicity

μ

3−k.Theexpandedsplineknotvectoron

γ

,

τττ

^μp^˜3^3−k−k,hassame sequence

τττ

,samedegree p3−^kandsamemultiplicityfunction

μ

3−^kexceptthat,incase

γ

isanextensionofasplitofM^, itisassignedfullmultiplicitytothepointof

τττ

correspondingtothejointvertexoftheextension.

In particular,if

γ

isan extension oftwo splits

γ

1

, γ

2 in M^,i.e.,

γ

isthe linkbetween

γ

1

, γ

2, thenthe firstandlast knotsintheexpandedsplineknotvectoron

γ

havefullmultiplicity.

Wecannowgivethedimensionincreasingformula.

Theorem3.9.GivenasplineLR-meshN ^{andanewk-split}

γ

suchthattheexpandedsplineknotvector

τττ

^μp^˜_3−k^3−k on

γ

haslength p3−^k

+

^r

+

^1withr

≥

^{1,thenthesplinespaceontherefinedsplinemesh}N

+ γ _:= (M + γ , μ ₊ μ

γ

,

ppp

)

hasdimension

dim

S(

N

+ γ ) =

^dim

S(

N

) +

^dim

S( τττ

^μ_p^˜₃³₋⁻_k^k

) =

^dim

S(

N

) +

^r

.

4. UnivariateB-splinesandbivariateB-splines

Inthissection werecallthedefinitionofB-splinesandtheir mainproperties.Inparticular,westate theknotinsertion algorithm,whichisusedforthedefinitionofLRB-splines.ForacompleteoverviewonB-splineswerefertode Boor(1978) andSchumaker(2007).

4.1. UnivariateB-splines

Definition4.1.For a non-decreasing sequence ttt

= (

t1

,

t2

, . . . ,

tp+²

)

we define a B-spline B

[

^ttt

] :

R

→

R ofdegree p

≥

⁰ recursivelyby

B

[

ttt

](

t

) =

^t

−

^t1

tp+¹

−

t1

B

[

t1

, . . . ,

tp+¹

](

t

) +

^tp+2

−

^t tp+²

−

t2

B

[

t2

, . . . ,

tp+²

](

t

),

(4)

whereeach time afractionwithzerodenominator appears, itistakenaszero.The initialB-splinesofdegree 0onttt are definedas

B

[

ti

,

ti+¹

](

t

) :=

^{1 ifti}

≤

^t

<

t_i+1

;

0 otherwise

;

^fori

=

1

, . . . ,

p

+

1

.

(5)

Thesequencettt iscalledknotvectorofB

[

^ttt

]

^andtj areitsknots.Aknottj hasmultiplicity

μ (

tj

)

ifitappears

μ (

tj

)

times inttt.

Proposition4.2(Properties).Givenadegreep

≥

^{0andaknotvectorttt}

= (

t1

, . . . ,

tp+²

)

,

•

^{supp B}

[

^ttt

] = [

^t1

,

tp+²

]

^,

•

^B

[

^ttt

]

^{restrictedtoeverynontrivialhalf-openelement}

[

^ti

,

ti+¹

)

isin

p,

•

^B

[

^ttt

]

^{isCp−μ(tj)}-continuousatanyknottjofmultiplicity

μ (

tj

)

.

Theorem4.3(knotinsertion).Givenadegreep andaknotvectorttt

= (

t₁

, . . . ,

t_p+2

)

,supposeweinsertaknot

ˆ

t

∈ (

t₁

,

t_p+2

)

.We obtaintwoknotvectorsttt1andttt2,consideringthefirstandthelastp

+

^2knotsrespectivelyin

(

t1

, . . . ,

t

ˆ , . . . ,

tp+²

)

.Thenthereexist

α

1

, α

2

∈ (

0

,

1

]

^suchthat

B

[

^ttt

] = α

1B

[

^ttt1

] + α

2B

[

^ttt2

] .

(6)

4.2. BivariateB-splines

Definition4.4.Consider a bidegree ppp

= (

p₁

,

p₂

)

. Let xxx

= (

x₁

, . . . ,

x_p1+2

)

and yyy

= (

y₁

, . . . ,

y_p2+2

)

be nondecreasing se- quences.WedefinethetensorproductB-spline B

[

^xxx

,

yyy

] :

R²

→

Rby

B

[

^xxx

,

yyy

] (

x

,

y

) :=

^B

[

^xxx

] (

x

)

B

[

^yyy

] (

y

),

(7)

whereB

[

^xxx

]

^andB

[

^yyy

]

^{aretheunivariateB-splinesdefinedonxxx andyyy}respectively.

Thepairxxx

,

yyyidentifiesatensormeshin

[

^x1

,

x_p1+2

] ×[

^y1

,

y_p2+2

]

^,M[^xxx

,

yyy

]

^{.Infact,aknotinthe}x-directionx_icorresponds tothe1-split

γ ₌

p

2+1

j=¹

γ

_j with

γ

_j

_{= {}

x_i

} × [

^yj

,

y_j+1

] ,

andmultiplicity

μ [

^xxx

,

yyy

]( γ

j

)

equalto themultiplicity ofx_i inxxx,forall j.Inthe samewaytheknots y_j inyyy identifythe 2-splitsinM[^xxx

,

yyy

]

^{andtheirassigned}multiplicities.

ThepropertiesofunivariateB-splinesareconservedbythetensorproductB-splines:

•

^suppB

[

^xxx

,

yyy

] = [

^x1

,

xp₁+²

] × [

^y1

,

yp₂+²

]

^.

•

^B

[

^xxx

,

yyy

]

^{isapiecewisebivariatepolynomialofbidegreeppp.}

•

^B

[

^xxx

,

yyy

]

^{isCpk−μ(γ)}-continuousacrosseachk-meshline

γ

ofM[^xxx

,

yyy

]

^.

Asintheunivariatecase,aftertheinsertionofaknotx

ˆ

inxxx,wedefinexxx1 andxxx2 considering in

(

x1

, . . . , ˆ

x

, . . . ,

xp1+²

)

the firstandlast p₁

+

^{2 knots}respectivelyandwecanwriteB

[

^xxx

,

yyy

]

^{intermsoftwoB-splinesdefinedonthetwonewpairsof} knotvectors

Fig. 3.SupportofB-splinesofbidegree(2,2)onameshM^ofmultiplicity1.Themeshisshownin(a).TheB-splineswhosesupportsaredepictedin(b) and(c)haveminimalsupportonM^{.Thetensormeshesdefinedbytheirknotsintheirsupportsare}highlightedwiththickerlines.Ontheotherhand,the B-splinein(d)doesnothaveminimalsupportonM^{:thecollectionofmeshlinescontainedinthedashedline}disconnectsthesupport.

B

[

^xxx

,

yyy

] = α

1B

[

^xxx1

,

yyy

] + α

2B

[

^xxx2

,

yyy

]

^with

α

1

, α

2

∈ (

0

,

1

].

⁽⁸⁾

Thesameholdswheninsertingaknot

ˆ

yinyyy.

Finally,considerasplinemeshN

= (M, μ ,

ppp

)

withM^{atensormesh.Thenthereexisttwosplineknotvectorsxxx}p1 and yyyp₂ thatidentifyM^,M

=

M[^xxxp1

,

yyyp₂

]

^{,asexplainedbeforeforthetensormesh}M[^xxx

,

yyy

]

^{inthesupportofB}

[

^xxx

,

yyy

]

^.Assume thatxxxp1 and yyyp2 havelength p1

+

^r1

+

^{1 and p}2

+

^r2

+

1 respectively,withr1

,

r2

≥

^{1.Wecanapplythe}Curry-Schoenberg Theoremoneachsplineknotvectorandstatethat

S(

N

) =

^span

{

^B

[

^xxxip₁

,

yyy_p^j₂

]}

^withi

=

¹

, . . . ,

r₁and j

=

¹

, . . . ,

r₂

,

wherexxxⁱ_p1

= (

xi

, . . . ,

xi+^p1+¹

) ⊆

^xxxp1 andyyy_p^j₂

= (

yj

, . . . ,

yj+^p2+¹

) ⊆

^yyyp2. 5. MinimalSupportB-splinesandLocallyRefinedB-splines

InthissectionwedefinefirsttheMinimalSupportB-splines,orMSB-splines,andthentheLocallyRefinedB-splines,or LRB-splines.AswewillseetheLRB-splinesarecreatedalgorithmically,refining,aftertheinsertionofasplitinthemesh, the B-splineswhose supportistraversedby thesplitthrough theknotinsertion procedure.Themain differencewiththe MSB-splinesisthattheselatterarenotalwaystheresultofaknotinsertion.Foragivenbidegree,theydependonlyonthe positionandmultiplicitiesofthemeshlinesinthemesh.

Definition5.1.Given a bivariate B-spline B

[

^xxx

,

yyy

]

^{and a split}

γ

, we say that

γ

traverses B

[

^xxx

,

yyy

]

^{if suppB}

[

^xxx

,

yyy

]\ γ

is not connected.

Definition5.2.GivenameshM^{andaB-spline B}

[

^xxx

,

yyy

]

^{,wesaythat B}

[

^xxx

,

yyy

]

^hassupportonM^{ifthemeshlinesin}M[^xxx

,

yyy

]

canbeobtainedasunionsofmeshlinesinM,andtheirmultiplicitiesinM[xxx

,

yyy

]

^{arelessthanorequaltothe}multiplicities ofthe correspondingmeshlinesinM^.Furthermore,wesaythat B

[

^xxx

,

yyy

]

^{hasminimalsupport on}M^{ifithassupporton} M^,the multiplicitiesof theinteriormeshlinesin M[^xxx

,

yyy

]

^{are equalto the}multiplicitiesof thecorresponding meshlines in M^{and thereis nosplit}

γ

inM\M[^xxx

,

yyy

]

^{that traverses B}

[

^xxx

,

yyy

]

^{. Givena splinemesh} N

= (

M

, μ ,

ppp

)

,the setof the minimalsupportB-splines,orMSB-splines,onN ofbidegreepppisdenotedasB^MS

(N )

.

Fig.3showsexamplesofB-splinesofbidegree

(

2

,

2

)

withsupportonameshofmultiplicity1.Inparticular,theB-splines consideredinFig.3(b)–(c)haveminimalsupport,whilethesupportoftheB-splineinFig.3(d)canbedisconnectedbythe split

γ

,visualizedbyadashedlineinthefigure.

GivenameshMandaB-spline B

[

^xxx

,

yyy

]

^{withsupportin}M,assumethatthereexistsa

(

k

, α )

–split

γ

inM\M[xxx

,

yyy

]

^that traverses B

[

^xxx

,

yyy

]

^{.Assumealsothatthemeshlinesin}

γ

haveall thesamemultiplicity m.Onecouldthen consider

α

asan extraknotofmultiplicityminthekthknotvectorsofB

[

^xxx

,

yyy

]

^(inxxxifk

=

^{1 andinyyyifk}

=

^{2)andperformtheknotinsertion} on B

[

^xxx

,

yyy

]

^{.TheresultinggeneratedB-splineswouldstillhavesupporton}M^{andeventuallytheywouldalsohaveminimal} supportonM^{.TheLRB-splinesaregeneratedthroughoutthe}constructionofanLR-meshfollowingthisprocedure.

Definition5.3.Givena spline LR-mesh N

= (M, μ ,

ppp

)

with M

=

MN final mesh of a mesh sequence asdescribed in Definition 2.6, the LRB-splineset B^LR

(N )

is provided algorithmically as follows. We start by considering the set B1 of standard B-splineson the initial coarse tensormesh M1.Then, for anyintermediate step Mi+¹

=

Mi

+ γ

i withi

=

1

, . . . ,

N

−

^{1 inthe}constructionoftheLR–mesh,weproduceanewsetofB-splinesBi+¹ bythefollowingalgorithm:

1. initializeBi+1

←

Bi,

2. aslongasthereexists B

[

^xxxj

,

yyy^j

] ∈

Bi+¹withnominimalsupportonMi+¹,

Fig. 4.(a)An LR-meshM^ofmultiplicity1.(b)SupportsofthebiquadraticLRB-splinesdefinedonM^{.(c)SupportofaminimalsupportB-splineonthe} meshnotinB^LR(N).

(a) applyknotinsertion:

∃

^B

[

^xxx₁^j

,

yyy₁^j

],

^B

[

^xxx₂^j

,

yyy₂^j

] :

^B

[

^xxxj

,

yyy^j

] = α

1B

[

^xxx₁^j

,

yyy₁^j

] + α

2B

[

^xxx₂^j

,

yyy₂^j

]

^, (b) updatetheset:Bi+1

← (

Bi+1

\{

^B

[

^xxxj

,

yyy^j

]} ) ∪ {

^B

[

^xxx₁^j

,

yyy₁^j

] ,

B

[

^xxx₂^j

,

yyy₂^j

]}

^,

3. B^LR

(N ) :=

BN.

Remark5.4.ForanysplineLR-meshN

= (M, μ ,

ppp

)

,spanB^LR

(N ) ⊆

^spanB^MS

(N ) ⊆

S(N

)

.IfM^{isatensormeshthen} B^LR

(N ) =

B^MS

(N )

and they are nothingmore than the standard bivariate B-splines. The Curry-Schoenberg Theorem ensuresthatspanB^LR

(N ) =

^spanB^MS

(N ) =

S(N

)

andtheelementsofB^LR

(M) =

B^MS

(M)

^arelinearlyindependent.

However,thereareothercaseswherethisequalityholds;wewillseetheminthenextsection.

Afterperforming the LR B-splinesgeneration algorithm, the functionscreatedwill generallynot sum toone. Forthis reason,inDokkenetal.(2013,Section7) isprovidedaprocedureforpositivescalingweightsoftheLRB-splinestoreinstate thepartitionofunity.

Example5.5(B^LR

(

N

) =

B^MS

(

N

)

).InFig.4(a)wehaveanLR-meshM^ofmultiplicity1.Supposeppp

= (

2

,

2

)

.Thismeshis obtainedbyinsertingtwo2-splitsandtwo1-splitsinatensormeshM1.InFig.4(b)weseethesupportsoftheLRB-splines onM^{,i.e.,theelementsof}B^LR

(

N

)

,withN

= (

M

,

1

, (

2

,

2

))

,obtainedbyrefiningtheB-splineswithnominimalsupport duringtheinsertionofthesplits.HoweverifwelookatthefinalmeshMinFig.4(a),weseethatthereisoneMSB-spline, whosesupportisdepictedinFig.4(c),notinB^LR

(N )

,definedonthemesh.

6. Hand-in-handprinciple

In this section we describe the spanning properties of the sets B^MS

(N )

and B^LR

(N )

. Any LR-mesh M

=

MN is defined through a sequence Mi+1

=

Mi

+ γ

i starting from a tensor mesh M1. We know that on N1

= (M

1

, μ

1

,

ppp

)

, spanB^MS

(N

1

) =

S(N1

)

aswell asspanB^LR

(N

1

) =

S(N1

)

. We want to preserve these equalities throughout the con- structionofMN fortworeasons.First,wemaximizetheapproximationpoweroftheconsideredB-splinesbecausethefull splinespaceisspanned, andsecond,since wehaveadimensionformulaforthesplinespace, wecanuseittodetermine iftheB-splinesare linearlydependentornot.Indeed,sincethey spanthewholesplinespace, ifthereare moreB-splines thanthedimension,theymustbelinearlydependent.

Definition6.1.Givena splineLR-meshN

= (

M

, μ ,

ppp

)

,assume thatspanB^MS

(

N

) =

S(N

)

,orspanB^LR

(

N

) =

S(N

)

re- spectively. Let

γ

be a newsplit andlet N

+ γ ₌ (M + γ , μ ₊ μ

γ

,

ppp

)

be therefined spline mesh. We saythat N

+ γ

goesMS-wise,orLR-wiserespectively,hand-in-handwithN ^ifspanB^MS

(N + γ ) =

S(N

+ γ )

,orspanB^LR

(N + γ ) =

S(N

+ γ )

respectively.

Inotherwords,goinghand-in-handmeansthatiftheconsideredB-splinesonthesplinemeshN ^{spanthewholespline} spaceS(N

)

,thenalsotherefinedB-splinesdefinedonN

+ γ

willspantherefinedsplinespaceS(N

+ γ )

.

Remark6.2.IfN

+ γ

goesLR-wisehand-in-handwithN^{,thenitalsogoesMS-wise}hand-in-handwithN^{.Thisistrivial} becauseB^LR

(N + γ ) ⊆

B^MS

(N + γ )

.Theconverseisnottrueingeneral.

In order to keep spanning the spline space during the construction of an LR-mesh, we have to ensure that all the intermediate spline meshesgo MS-wise,orLR-wise, hand-in-hand. Acondition to achieve thisis statedin thefollowing result,whichisareformulationofDokkenetal.(2013,Theorem5.10).