Spaces of generalized splines over T-meshes a a Cesare Bracco and Fabio Roman aDepartment of Mathematics “G. Peano”- University of Turin 4 V. Carlo Alberto 10, Turin 10123, Italy 1 0 2 p Abstract e S We consider a class of non-polynomial spline spaces over T-meshes, that is, of 5 spaces locally spanned both by polynomial and by suitably-chosen non-polynomial 2 functions, which we will refer to as generalized splines over T-meshes. For such ] spaces, we provide, undercertain conditions, a dimension formula and a basis based A on the notion of minimal determining set. We explicitly examine some relevant N cases, which enjoy a noteworthy behaviour with respect to differentiation and in- . h tegration; finally, we also study the approximation power of the just constructed t spline spaces. a m [ Keywords:T-mesh, generalized splines, dimension formula, basis functions, approxi- mation power. 3 v 1 1 1 Introduction 9 7 . 1 The T-splines, first introduced in [15] and [16], represent a significant advancement in 0 4 CAD and CAGD techniques, with relevant applications to differential problems, in par- 1 ticular in the framework of isogeometric analysis (see, e.g., [5] and [1]). The spline spaces : v over T-meshes are a closely related notion, first introduced by Deng et al. in [6] and i X further studied by the same authors and several others (see, e.g., [9], [10], [13] and [14]). r The basic idea consists of considering spaces of spline functions which are polynomials ofa a certain degree in each of the cells of theT-mesh, which, unlike the classical tensor-product meshes, allows T-junctions, that is, vertices where only three edges meet. This paper is devoted to the study of the Generalized spline spaces over T-meshes, a class of non-polynomial spline spaces, which essentially generalize the concept of spline space over a T-mesh: roughly speaking, they are locally spanned by polynomials and some suitable non-polynomial functions. The relevance of this class of spline spaces and some of the basic concepts related to it have been only recently discussed in some international conferences. The same kind of non-polynomial functions have been recently used also to construct non-polynomial T-splines (see, e.g., [3]), and non-polynomial hierarchical splines spaces (see [12]). The goal of this work is to carry out a rigorous and deep study of the class of Generalized splines over T-meshes, including general results about 1 the space dimension, the approximation power and noteworthy cases, which, as far as we know, are still missing in the literature. The introduction and the study of these non-polynomial spaces is justified by at least two reasons. First of all, the presence of non-polynomial functions allows to exactly reproduce certain shapes which can only be approximated by polynomial splines or NURBS (for example relevant curves like helices, cycloids, catenaries, or other transcendental curves). Moreover, as we will also point out inSection 4, choosing suitable non-polynomial functionsalsoallows aneasier computation of derivatives and integrals of certain surfaces with respect to using NURBS (see also [11], [7]). Starting from some of the results obtained in [4] about a noteworthy class of univariate non-polynomial spaces, we define generalized spline spaces over T-meshes and construct a local representation in the Bernstein-B´ezier fashion for their elements. For the above spaces we first provide the construction of a basis and a dimension formula by using the properties of the local Bernstein-B´ezier representation and by generalizing to the non- polynomial case the techniques proposed for the polynomial one in [14]. Then, we show and discuss some noteworthy cases of generalized spline spaces over a T- mesh, which have a good behaviour w.r.t. differentiation and integration. Such a feature is very useful for the applications of the considered spaces, especially in the isogeometric analysis. Moreover, we also study the approximation power of the just constructed spline spaces. In particular, we do it by constructing a quasi-interpolant based on some new local ap- proximants, whose construction is not trivial. In fact, the results about the univariate non-polynomial Hermite interpolants given in [4] cannot be directly extended to the bi- variate case. On the other hand, also the bivariate averaged Taylor expansions used in [14] cannot be simply adapted to the non-polynomial case we consider here. There- fore, we instead defined a new local Hermite interpolant belonging to the non-polynomial spline space, whose existence is proved by using certain assumptions made about the non-polynomial functions spanning the space, as carefully explained in Section 5. This approach allows us to get essentially the same approximation order as in the polynomial case. The paper is organized as follows. Section 2 includes several preliminary arguments about the non-polynomial spaces we will use to define the new spline spaces, including some important properties about the derivatives of the basis functions and the basic concepts about T-meshes. Section 3 presents the new generalized spline spaces over T-meshes, and includes a detailed proof of the dimension formula and of the construction of the basis. Section 4 deals with the issue of suitable choices of the spaces in order to get a good behaviour of the spaces themselves w.r.t. differentiation and integration. Finally, Section 5 is devoted to the study of the approximation power of the constructed generalized spline space. 2 Preliminaries The spaces we will consider are of the type Pn ([a,b]) := spanh1,s,...,sn−3,u(s),v(s)i, s ∈ [a,b], 3 ≤ n ∈ IN, (1) u,v 2 where u,v ∈ Cn([a,b]); for n = 2 we set P2 ([a,b]) := spanhu(s),v(s)i, s ∈ [a,b]. u,v We assume that dim Pn ([a,b]) = n; moreover, in order to prove some of the properties u,v we are about to present, we will sometimes require the following additional conditions on (cid:0) (cid:1) Pn ([a,b]) u,v ∀ψ ∈ Pn ([a,b]), if ψ(n−2)(s ) = ψ(n−2)(s ) = 0, s ,s ∈ [a,b], s 6= s u,v 1 2 1 2 1 2 then ψ(n−2)(s) = 0, s ∈ [a,b]; (2) ∀ψ ∈ Pn ([a,b]), if ψ(n−2)(s ) = ψ(n−1)(s ) = 0, s ∈ (a,b), u,v 1 1 1 then ψ(n−2)(s) = 0, s ∈ [a,b]. (3) In the following, we will explicitly mention when such conditions are needed. 2.1 Normalized positive basis and its properties In this subsection we consider a normalized positive basis for the space Pn ([a,b]). The u,v procedure to obtain it and its fundamental properties are known and can be found in [4]. Therefore here we will just recall the main results obtained in [4], omitting the proofs. We will instead prove Property 2.4, which will be crucial in order to obtain some results later in the paper. In this Section we assume that the condition (2) holds. The normalized positive basis can be constructed by using the following integral re- currence relation. By (2), there exist unique elements U and U belonging to 0,1,n−1 1,1,n−1 spanhu(n−2),v(n−2)i satisfying U (a) = 1, U (b) = 0, 0,1,n−1 0,1,n−1 U (a) = 0, U (b) = 1, (4) 1,1,n−1 1,1,n−1 and U (s),U (s) > 0, s ∈ (a,b). (5) 0,1,n−1 1,1,n−1 Moreover, we define, for k = 2,...,n−1 and n ≥ 3 U (s) = 1−V (s) 0,k,n−1 0,k−1,n−1 U (s) = V (s)−V (s), 1 ≤ i ≤ k −1 i,k,n−1 i−1,k−1,n−1 i,k−1,n−1 U (s) = V (s), (6) k,k,n−1 k−1,k−1,n−1 where s V (s) = U /d dt, (7) i,k,n−1 i,k,n−1 i,k,n−1 Za and b d (s) = U dt, i,k,n−1 i,k,n−1 Za for i = 0,...,k, k = 1,...,n − 2. Note that (4) and (5) hold also in the particular case n = 2, and then U and U are a positive basis for P2 ([a,b]). The following results 0,1,1 1,1,1 u,v can be proved about the just defined functions. 3 Theorem 2.1. For k = 2,...,n−1 and n ≥ 3, the set of functions {U ,...,U } 0,k,n−1 k,k,n−1 is a basis for the space spanh1,s,...,sk−2,u(n−k−1)(s),v(n−k−1)(s)i. Moreover, itis a normalizedpositivebasis, that is, satisfiesthe conditions k U (s) = i=0 i,k,n−1 1 and U (s) > 0 for s ∈ (a,b), i = 0,...,k. i,k,n−1 P Corollary 2.2. The set of functions {U ,...,U } is a normalized positive 0,n−1,n−1 n−1,n−1,n−1 basis for the space Pn ([a,b]), n ≥ 3, U = B , where {B }n−1 satisfy u,v i,n−1,n−1 i,n−1 i,n−1 i=0 n−1B (s) = 1 and B (s) > 0 for s ∈ (a,b), i = 0,...,n−1. For n = 2, the set i=0 i,n−1 i,n−1 {U ,U } is a positive basis of P2 ([a,b]). P0,1,1 1,1,1 u,v Since in the case n = 2 we cannot, in general, guarantee the construction of a normalized positive basis, in the following we will assume n ≥ 3. As a consequence of the results given in Sections 4 and 6 of [4], we get the following property. Property 2.3. For i = 0,...,k, k = 2,...,n−1 and n ≥ 3, we have (j) U (a) = 0, j = 0,...,i−1, i,k,n−1 (j) U (b) = 0, j = 0,...,k−i−1. i,k,n−1 In particular, if we consider k = n−1, we have (j) B (a) = 0, j = 0,...,i−1, i,n−1 (j) B (b) = 0, j = 0,...,n−i−2. i,n−1 Property 2.4. For k = 2,...,n−1 and n ≥ 3, we have (i) U (a) 6= 0, i = 0,...,k−1, i,k,n−1 (k−i) U (b) 6= 0, i = 1,...,k. i,k,n−1 In particular, if we consider k = n−1, we have (i) B (a) 6= 0, i = 0,...,n−2, (8) i,n−1 (n−i−1) B (b) 6= 0, i = 1,...,n−1. (9) i,n−1 Proof. First, let us prove (8) by induction. For k = 2, (8) holds, since from (4), (6) and (7) we get a U (a) = 1−V (a) = 1− U (t)/d dt = 1−0 = 1, 0,2,n−1 0,1,n−1 0,1,n−1 0,1,n−1 Za U (a) U (a) 1 (1) 0,1,n−1 1,1,n−1 U (a) = D[V (s)−V (s)] = − = −0 6= 0. 1,2,n−1 0,1,n−1 1,1,n−1 s=a d d d 0,1,n−1 1,1,n−1 0,1,n−1 4 Now, if (8) holds for k, it must be true for k +1 as well, since we have a U (a) = 1−V (a) = 1− U (t)/d dt = 1−0 = 1, 0,k+1,n−1 0,k,n−1 0,k,n−1 0,k,n−1 Za (i−1) (i−1) (i−1) U (a) U (a) U (a) (i) i−1,k,n−1 i,k,n−1 i−1,k,n−1 U = − = 6= 0, i,k+1,n−1 d d d i−1,k,n−1 i,k,n−1 i−1,k,n−1 where we used (6), (7), Property 2.3 and the induction hypothesis. Analogously we can (cid:3) prove (9). Note that the above constructed basis is not only normalized positive, but it is also a Bernstein basis. 2.2 Some definitions on T-meshes WewillnowrecallthedefinitionofT-meshandofsomerelatedobjects, usingthenotations of [14]. Note that the concept of T-mesh we will consider here may slightly differ from other ones in the literature, such as themore general used in [2], which allows the presence not only of T-junctions, but of L-junctions and I-junctions as well. Definition 2.5. A T-mesh is a collection of axis-aligned rectangles ∆ = {R }N such i i=1 that the domain Ω ≡ ∪ R is connected and any pair of rectangles (which we will call i i cells) R ,R ∈ ∆ intersect each other only at points on their edges. i j An example of T-mesh where Ω = [−1,6]×[−1,5] Note that this definition does not imply that the domain Ω is rectangular and allows the presence of holes in it. Tensor-product meshes are a particular case of T-meshes. If a vertex v of a cell belonging to ∆ lies in the interior of an edge of another cell, then we call it a T-junction. Definition 2.6. Given a T-mesh ∆, a line segment e = hw ,w i connecting the vertices 1 2 w and w is called edge segment if there are no vertices lying in its interior. Instead, 1 2 5 if all the vertices lying in its interior are T-junctions and if it cannot be extended to a longer segment with the same property, then we call it a composite edge. In the following, we will consider T-meshes which are regular and have no cycles, in the sense of the following definitions (see [14] for more details). An example of regular T-mesh. An example of non-regular T-mesh. Definition 2.7. A T-mesh ∆ is regular if for each of its vertices w the set of all rectangles containing w has a connected interior. Definition 2.8. Let w ,...,w be a collection of T-junctions in a T-mesh ∆ such that w 1 n i lies in the interior of a composite edge having one of its endpoints at w (we assume i+1 w = w ). Then w ,...,w are said to form a cycle. n+1 1 1 n The sequence w ,w ,w ,w is a cycle. 1 2 3 4 6 3 Spaces of generalized splines on T-meshes In this Section, we define the spaces of generalized splines over T-meshes, and we study their dimension by constructing a basis. The results obtained can be considered a gen- eralization to non-polynomial splines spaces over T-meshes of the ones proved in [14] for the basic polynomial case. 3.1 Basics Let ∆ be a regular T-mesh without cycles, and let 0 ≤ r < n − 1, 0 ≤ r < n − 1, 1 1 2 2 where r ,r ,n ,n are integers and n ,n ≥ 2. Later on, we will also use the notation 1 2 1 2 1 2 r = (r ,r ) and n = (n ,n ). We define the space of generalized splines over the T-mesh 1 2 1 2 ∆ of bi-order n and smoothness r as GSn,r(∆) = {p(s,t) ∈ Cr(Ω) : p| ∈ Pn (R) ∀R ∈ ∆}, (10) u,v R u,v r where Ω = ∪ R, C (Ω) denotes the space of functions p such that their derivatives R∈∆ DiDjp are continuous for all 0 ≤ i ≤ r and 0 ≤ j ≤ r , and the space Pn is defined as s t 1 2 u,v Pn (R) = spanhg (s)g (t) : g ∈ Pn1 ([a ,b ]), g ∈ Pn2 ([c ,d ])i, (11) u,v 1 2 1 u1,v1 R R 2 u2,v2 R R with R = [a ,b ] × [c ,d ] and u ,v ∈ Cn1([a ,b ]), u ,v ∈ Cn2([c ,d ]) such that R R R R 1 1 R R 2 2 R R dim Pn1 ([a ,b ]) = n and u1,v1 R R 1 dim Pn2 ([c ,d ]) = n , and satisfying both (2) and (3). In other words, GSn,r(∆) (cid:0) u2,v2 R R (cid:1) 2 u,v is a space of spline functions which, restricted to each cell R, are products of functions (cid:0) (cid:1) belonging to spaces of type (1). We introduce now on each cell R a Bernstein-B´ezier representation for the elements of GSn,r(∆) based on the Bernstein basis of Pn1 ([a ,b ]) and Pn2 ([c ,d ]) constructed u,v u1,v1 R R u2,v2 R R in Theorem 2.2; therefore, we need to assume that (2) is satisfied both by Pn1 ([a ,b ]) u1,v1 R R and Pn2 ([c ,d ]). Let us denote by {BR }n1−1 and {BR }n2−1 the Bernstein basis u2,v2 R R i,n1−1 i=0 i,n2−1 i=0 of, respectively, Pn1 ([a ,b ]) and Pn2 ([c ,d ]), to stress the dependence of the basis u1,v1 R R u2,v2 R R on the coordinates a ,b ,c ,d of the vertices of the cell R. For any p ∈ GSn,r(∆), we R R R R u,v can then give on the cell R the following representation n1−1n2−1 p| (s,t) = cRBR (s)BR (t), (12) R ij i,n1−1 j,n2−1 i=0 j=0 X X where cR ∈ IR are suitable coefficients. Let us define the set of domain points associated ij to R Dn,R = {ξiRj}ni=1−0,1j,=n02−1, with (n −1−i)a +ib (n −1−j)c +jd ξR = 1 R R, 2 R R , i = 0,...,n −1, j = 0,...,n −1. ij n −1 n −1 1 2 1 2 (cid:16) (cid:17) 7 We can then define the set of domain points for a given T-mesh ∆ as Dn,∆ = Dn,R, R∈∆ [ where we assume that multiple appearances of the same point are allowed. If we set BR(s,t) = BR (s)BR (t), where ξR = ξ, ξ i,n1−1 j,n2−1 ij then, for each R ∈ ∆, we can re-write (12) in the more compact form p| (s,t) = cRBR(s,t), R ξ ξ ξ∈XDn,R which we call Bernstein-B´ezier form; we refer to the cR as the B-coefficients. It is then ξ clear that any element of the space GSn,r(∆) is completely determined by a set of B- u,v coefficients {c } . Of course, not every choice of the B-coefficients corresponds to an ξ ξ∈Dn,∆ element in the spline space, since smoothness conditions must be satisfied. 3.2 Smoothness conditions In order to study the consequences of the smoothness conditions required for GSn,r(∆) u,v on the determination of the B-coefficients of an element of the space, first we need to recall some more concepts about domain points. Let R = [a ,b ]×[c ,d ] ∈ ∆, w = (a ,c ), and µ = (µ ,µ ) with µ ≤ n −1 and R R R R R R 1 2 1 1 µ ≤ n −1. We call the set DR(w) = {ξ }µ1,µ2 the disk of size µ around w. The disks 2 2 µ ij i=0,j=0 around the other vertices of R can be defined analogously. Moreover, we say that the points ξR with 0 ≤ i ≤ ν lie within a distance ν from the edge e = {a } ×[c ,d ] and ij R R R we use the notation d(ξR) ≤ ν. Analogous notations hold for the other edges of R. ij Moreover, we can define the set of domain points D (w) = DR, µ µ R[∈∆w where ∆ ⊂ ∆ contains only the cells having w as one of their vertices and multiple w appearances of a point are allowed in the union. Given a composite edge e, an edge e˜ lying on e and a vertex w of e˜, if d(w,e˜) ≤ ν, then we write that d(w,e) ≤ ν as well. Thefollowinglemma isakey steptobeabletounderstandtheinfluence ofthesmoothness conditions and to get a dimension formula for the space. Lemma 3.1. Let p ∈ GSn,r(∆) and let w be a vertex of ∆. Let us considertwo cells R and u,v R˜ with vertices (in counter-clockwise order) w,w ,w ,w and w,w ,w ,w , respectively. 2 3 4 5 6 7 If the coefficients c , ξ ∈ DR(w) are given, then the coefficients c , η ∈ DR˜(w) are uniquely ξ r η r determined by the smoothness conditions at w. 8 Proof. We prove the lemma for the case where w is the upper-right corner of R = ˜ [a ,b ]×[c ,d ]andthelower-left cornerofR = [a ,b ]×[c ,d ], thatis, w = (b ,d ) = R R R R R˜ R˜ R˜ R˜ R R (a ,c ). First, let us consider the partial derivatives of p| R˜ R˜ R˜ n1−1n2−1 DhDkp| (a ,c ) = cR˜DhBR˜ (a )DkBR˜ (c ), 0 ≤ h ≤ r , 0 ≤ k ≤ r . s t R˜ R˜ R˜ ij s i,n1−1 R˜ t j,n2−1 R˜ 1 2 i=0 j=0 X X Since by Corollary 2.2 BR˜ (s) = U (s) and BR˜ (t) = U (t), using i,n1−1 i,n1−1,n1−1 j,n2−1 j,n2−1,n2−1 Property 2.3 gives that DhBR˜ (a ) = 0, h < i ≤ n −1, s i,n1−1 R˜ 1 DkBR˜ (c ) = 0, k < j ≤ n −1. t j,n2−1 R˜ 2 Therefore, h k DhDkp| (a ,c ) = cR˜DhBR˜ (a )DkBR˜ (c ). s t R˜ R˜ R˜ ij s i,n1−1 R˜ t j,n2−1 R˜ i=0 j=0 XX Now let us compute the partial derivatives of p| R n1−1n2−1 DhDkp| (b ,d ) = cRDhBR (b )DkBR (d ), 0 ≤ h ≤ r , 0 ≤ k ≤ r . s t R R R ij s i,n1−1 R t j,n2−1 R 1 2 i=0 j=0 X X Since by Corollary 2.2 BR (s) = U (s) and BR (t) = U (t), using i,n1−1 i,n1−1,n1−1 j,n2−1 j,n2−1,n2−1 Property 2.3 gives that DhBR (b ) = 0, 0 ≤ i < n −1−h, s i,n1−1 R 1 DkBR (d ) = 0, 0 ≤ j < n −1−k. t j,n2−1 R 2 Therefore, n1−1 n2−1 DhDkp| (b ,d ) = cRDhBR (b )DkBR (d ). s t R R R ij s i,n1−1 R t j,n2−1 R i=nX1−1−hj=nX2−1−k r Requiring the C smoothness at w is then equivalent to the linear system composed of the equations h k n1−1 n2−1 cR˜DhBR˜ (a )DkBR˜ (c ) = cRDhBR (b )DkBR (d ), ij s i,n1−1 R˜ t j,n2−1 R˜ ij s i,n1−1 R t j,n2−1 R Xi=0 Xj=0 i=nX1−1−hj=nX2−1−k (13) for h = 0,...,r , k = 0,...,r . 1 2 Note that in this case we have {c } = {cR}n1−1,n2−1 , that is, the (r + ξ ξ∈DrR(w) ij i=n1−1−r1,j=n2−1−r2 1 1)× (r + 1) B-coefficients associated to R given by hypothesis are exactly the ones on 2 the right-hand of equations (13). Analogously, {cη}η∈DrR˜(w) = {cRi˜j}ir=1,0r,2j=0, which means that the (r +1)×(r +1) B-coefficients associated to R˜ are the unknowns of the system 1 2 (13). It is easy to observe that, if we organize the equations according to the order of 9 the derivatives, the matrix of the system is lower triangular. Moreover, the entries on the diagonal of the matrix, that is, DhBR˜ (a )DkBR˜ (c ), h = 0,...,r , k = 0,...,r , s h,n1−1 R˜ t k,n2−1 R˜ 1 2 (cid:3) are not zero because of Property 2.4. After having studied the influence of smoothness around a vertex, we now study the situation around edges. Given a composite edge e, we will use the following notation r , if e is vertical, 1 r = e (r2, if e is horizontal, D , if e is vertical, s D = e (Dt, if e is horizontal, n , if e is vertical, 2 n = e (n1, if e is horizontal, u , if e is vertical, 2 u = e (u1, if e is horizontal, v , if e is vertical, 2 v = e (v1, if e is horizontal. Moreover, to get the following results we will assume that u ,v are such that for each 1 1 horizontal edge segment f = [a ,b ]×{c } f f f dimPn1 ([a ,b ]) = n , (14) u1,v1 f f 1 and that u ,v are such that for each vertical edge segment f = {a }×[c ,d ] 2 2 f f f dimPn2 ([c ,d ]) = n ,. (15) u2,v2 f f 2 Lemma 3.2. Let e be a composite edge of ∆ with endpoints w and w , and let p ∈ 1 5 GSn,r(∆). For any 0 ≤ ν ≤ r , Dνp| is a univariate function belonging to the space u,v e e e Pne ([w ,w ]), where w ,w ∈ IR are the abscissas/ordinates of w ,w . ue,ve 1,e 5,e 1,e 5,e 1 5 Proof. The Lemma can be trivially proved with the same arguments used in [14] for the (cid:3) polynomial case, thanks to the assumptions (14) and (15). Let us now consider a cell R with vertices w ,w ,w ,w and another cell R˜ with e 1 2 3 4 e vertices w ,w ,w ,w . Moreover we assume that w and w lie on e as well (the other 5 6 7 8 2 8 cases are analogous). Let us use the notation r1,n2−r2−2 ξRe , if e is vertical, ij M = i=0,j=r2+1 (16) e n on1−r1−2,r2  ξRe , if e is horizontal.  ij i=r1+1,j=0 n o Inotherwords, thesetMe includesallthedomainpointsξ lyingoutsidethedisksDrRe(w1) and DRe(w ) and satisfying d(ξ,e) ≤ r . r 2 e 10