C¹-Quartic Butterfly-Spline Interpolation on Type-1 Triangulations

Abstract

In this paper, we construct and analyse C ¹ quartic interpolating splines on type-1 triangulations, approximating regularly distributed data. This is achieved by defining the associated Bernstein-Bézier coefficients from point values of the function to be approximated in such a way that C ¹ regularity is obtained for enough regular functions as well as the optimal order of approximation. We construct such interpolating splines by combining a quasi-interpolating spline with one step of an interpolatory subdivision scheme. Numerical tests confirming the theoretical results are provided.

1 Introduction

The use of spline interpolation and quasi-interpolation for the approximation of functions and data is widely developed in the literature and many approaches have been proposed. Schemes based on the construction of finite elements, macro-elements and local stable minimal determining sets for general (refined or not) triangulations of a polygonal domain have been proposed (see e.g. [16, 17] and references therein), as well as the definition of such approximating splines in the space spanned by a family of compactly supported functions (see e.g. [8] and [20]). In the uniform case, box splines have been also extensively used (see e.g. [5, 10, 24] and references therein, and [3, 4, 18, 19]), and a new procedure was introduced based on the definition of the Bernstein-Bézier (BB-) coefficients of the splines on each triangle in the partition by using only point values in a neighbourhood of the triangle. The BB-coefficients are properly defined to produce globally C ¹ splines and to achieve the required polynomial reproduction (see e.g. [1, 14, 21, 23] and [22] for the 3D case).

The C ¹ quartic scheme exact on cubic polynomials introduced in [23] is a particular case of a general family derived in [2] that depends on some free parameters. The BB-coefficients with respect to any triangle of the quasi-interpolating splines are defined from the values at a large number of points lying in a neighbourhood of the triangle, so it is quite natural to think about reducing the number of evaluations needed to compute the BB-coefficients. This issue is dealt with in [2], where it is proved that only evaluation at vertices and midpoints of edges of triangles are needed.

In this paper, we follow this approach and combine a quasi-interpolating spline with one step of the so called modified Butterfly interpolatory subdivision scheme to construct C ¹ quartic interpolating splines on regular type-1 triangulations, whose BB-coefficients are defined uniquely from the values at the vertices of the triangulation.

The organization of the paper is as follows. In Sect. 2, some results on the representation of C ¹-quartic splines on three-directional triangulations are recalled, as well as the notations to be used in the paper. In Sect. 3 we recall the family of quasi-interpolation operators studied in [2]. In particular, all of them depend on some free parameters, so we propose some specific choices for them. In Sect. 4 we present the construction of a family of interpolating splines, obtained by combining the quasi-interpolating splines of Sect. 3, with one step of the modified Butterfly interpolatory subdivision scheme. We also discuss the approximation properties of the corresponding operators. Finally, in Sect. 5, we propose some numerical tests to confirm the theoretical results established in the previous sections.

2 Notations and Preliminaries

We consider the type-1 triangulation Δ defined by the directions $d_{1}:=\left ( h,h\right )$, $d_{2}:=\left ( h,-h\right )$ and d ₃ := d ₁ + d ₂, with h > 0. Its vertices v _i,j are linear combinations of directions d ₁ and d ₂ with integer coefficients, i.e. v _i,j := id ₁ + jd ₂, $i,j\in \mathbb {Z}$. The two-dimensional lattice $\mathcal {V}:=\left \{ v_{i,j}:i,j\in \mathbb {Z}\right \}$ decomposes the real plane into parallelograms P _i,j with vertices v _i,j, v _i,j+1, v _i+1,j+1 and v _i+1,j (see Fig. 1(left)), each of which is subdivided into two triangles T _i,j and $\widetilde {T}_{i,j}$ obtained by connecting the vertices v _i,j and v _i+1,j+1, so that

$$\displaystyle \begin{aligned} \varDelta:=\bigcup_{i,j\in\mathbb{Z}}\left( T_{i,j}\cup\widetilde{T} _{i,j}\right) . \end{aligned}$$

The triangles sharing a vertex v _i,j determine an hexagon, denoted by H _i,j (see Fig. 1(right)).

Fig. 1

The triangulation Δ (left) and the hexagon H _i,j (right)

The approximating splines will be constructed in the space

$$\displaystyle \begin{aligned} \mathcal{S}_{4}^{1}\left( \varDelta\right) :=\left\{ s\in C^{1}\left( \mathbb{R}^{2}\right) :s_{\mid T}\in\mathbb{P}_{4},\ \text{for all } T\in\varDelta\right\} , \end{aligned}$$

where $\mathbb {P}_{4}$ stands for the space of bivariate quartic polynomials. Such splines will be defined by directly setting their BB-coefficients on the triangles of Δ (see e.g. [16]). The restriction to a triangle T ∈ Δ with vertices v ₀, v ₁ and v ₂ of a spline $s\in \mathcal {S}_{4}^{1}\left ( \varDelta \right )$ can be expressed as

$$\displaystyle \begin{aligned}s_{\mid T}={\displaystyle\sum_{i+j+k=4}} c_{i,j,k}^{T}B_{i,j,k}^{T}, \end{aligned}$$

where $B_{i,j,k}^{T}:=\frac {4!}{i!j!k!}b_{0}^{i}b_{1}^{j}b_{2}^{k}$, i, j, k ≥ 0, i + j + k = 4, are the Bernstein polynomials of degree 4 associated with T and the barycentric coordinates $\left ( b_{0},b_{1},b_{2}\right )$ w.r.t. T satisfy the equalities $\left ( x,y\right ) =b_{0}v_{0}+b_{1}v_{1}+b_{2}v_{2},\ b_{0}+b_{1}+b_{2}=1$ for $\left ( x,y\right ) \in T$. To alleviate the notation, no reference is made to the triangle with respect to which the barycentric coordinates are determined.

Each BB-coefficient $c_{i,j,k}^{T}$ of the quartic polynomial s _∣T is associated to the domain point $\xi _{i,j,k}^{4}:=\left ( iv_{0}+jv_{1}+kv_{2}\right ) /4$ in T. Let $\mathcal {D}_{4}$ be the subset of the domain points arising when all triangles in Δ are run. Each vertex gives rise to a single point in $\mathcal {D}_{4}$. The same is applicable for any domain point on an common edge to two triangles (see Fig. 2). If quadratic splines are considered instead of quartic splines, their BB-representations give rise to coefficients associated with the domain points $\xi _{i,j,k}^{2}:=\left ( iv_{0}+jv_{1}+kv_{2}\right ) /2$, from which the subset $\mathcal {D}_{2}$ is defined. Finally, the subset $\mathcal {D}_{1}$ is the collection of all vertices of the triangulation Δ (see Fig. 3).

Fig. 2

The points of $\mathcal {D}_{4}$ relative to H _i,j

Fig. 3

The points of $\mathcal {D}_{2}$ (left) and $\mathcal {D}_{1}$ (right) relative to H _i,j

Moreover, we define $\mathcal {D}_{\ell }:=\bigcup _{i,j}\mathcal {D}^{i,j}_{\ell }$, ℓ = 2, 4 with

• $\mathcal {D}^{i,j}_{4}:=\left \{ v_{i,j}\right \}$ ∪ $\left \{ e_{i,j}^{k,m},k,m\in \left \{ 0,1\right \} ,k+m\neq 0\right \}$

  ∪ $\left \{u_{i,j}^{k,m},z_{i,j}^{k,m},k,m\in \left \{ -1,0,1\right \} ,k+m\neq 0\right \}$, where

  • $e_{i,j}^{k,m}$ is the midpoint of $\left [ v_{i,j},v_{i+k,j+m}\right ]$,

  • $u_{i,j}^{k,m}:=\frac {1}{4}\left ( 3v_{i,j}+v_{i+k,j+m}\right )$,

  • $z_{i,j}^{k,m}:=\frac {1}{4}\left ( 2v_{i,j}+v_{i+k,j+m}+v_{r,s}\right )$, with v _r,s the third vertex of

    $\left [ v_{i,j},v_{i+k,j+m},v_{r,s}\right ] \in \varDelta$ counting counterclockwise;

• $\mathcal {D}^{i,j}_{2}:=\left \{ v_{i,j},e_{i,j}^{1,0},e_{i,j}^{0,1},e_{i,j}^{1,1}\right \}$.

3 C ¹ Quartic Quasi-interpolating Splines on $\mathcal {D}_{2}$

In order to make the paper self-contained, here we briefly recall how the quasi-interpolating spline $Q_{4,2}f\in \mathcal {S}_{4}^{1}\left ( \varDelta \right )$ in [2] is defined. Such a spline is constructed using the values of f on $\mathcal {D}_{2}$.

We take advantage of the fact that Δ is a uniform triangulation to define the BB-coefficients of the restriction of the quasi-interpolating Q _4,2 f to each triangle. For instance, we write the restriction of Q _4,2 f to the triangle T _i,j as

$$\displaystyle \begin{aligned} Q_{4,2}f_{\mid T_{i,j}} = & c\left( v_{i,j}\right) B_{4,0,0}^{T_{i,j}}+c\left( u_{i,j}^{1,1}\right) B_{3,1,0}^{T_{i,j}}+c\left( u_{i,j}^{1,0}\right) B_{3,0,1}^{T_{i,j}}\\ &+c\left( e_{i,j}^{1,1}\right) B_{2,2,0}^{T_{i,j}} +c\left( z_{i,j}^{1,1}\right) B_{2,1,1}^{T_{i,j}} +c\left( e_{i,j}^{1,0}\right) B_{2,0,2}^{T_{i,j}}\\ & +c\left( u_{i+1,j+1}^{-1,-1}\right) B_{1,3,0}^{T_{i,j}}+c\left( z_{i+1,j+1j}^{0,-1}\right) B_{1,2,1}^{T_{i,j}}+c\left( z_{i+1,j}^{-1,0}\right) B_{1,1,2}^{T_{i,j}} \\ & +c\left( u_{i+1,j}^{-1,0}\right) B_{1,0,3}^{T_{i,j}}+c\left(v_{i+1,j+1}\right) B_{0,4,0}^{T_{i,j}}+c\left( u_{i+1,j+1}^{0,-1}\right) B_{0,3,1}^{T_{i,j}}\\ & +c\left( e_{i+1,j}^{0,1}\right) B_{0,2,2}^{T_{i,j}} +c\left( u_{i+1,j}^{0,1}\right) B_{0,1,3}^{T_{i,j}}+c\left(v_{i+1,j}\right) B_{0,0,4}^{T_{i,j}}, \end{aligned} $$

where the notation $c\left ( p\right )$ is used for the BB-coefficient relative to the domain point $p\in \mathcal {D}_{4}$.

Moreover, once defined the BB-coefficients relative to T _i,j, those corresponding to the other five triangles around the vertex v _i,j are defined by translation and/or rotation.

In order to obtain an interpolatory spline at the vertices, we define $c\left ( v_{i,j}\right ) :=f\left ( v_{i,j} \right )$.

The domain points $\,p\in \mathcal {D}_{4}$ have been labelled as u, e and z-points. Their BB-coefficients will be defined as linear combinations of the values of f at 19 points in $\mathcal {D}_{2}$ (see Fig. 3). As an example,

$$\displaystyle \begin{aligned} c\left( u_{ij}^{1,1}\right) = &\gamma_{0}f\left( v_{ij}\right)+\gamma_{1}f\left( e_{i,j}^{1,1}\right) +\gamma_{2}f\left( e_{i,j}^{1,0}\right) +\gamma_{3}f\left( e_{i,j-1}^{0,1}\right) +\gamma_{4}f\left(e_{i-1,j-1}^{1,1}\right) \\ & +\gamma_{5}f\left( e_{i-1,j}^{1,0}\right)+\gamma_{6}f\left( e_{i,j}^{0,1}\right)+\gamma_{7}f\left( v_{i+1,j+1}\right) +\gamma_{8}f\left(e_{i+1,j}^{0,1}\right) \\ & +\gamma_{9}f\left( v_{i+1,j}\right) +\gamma_{10}f\left( e_{i,j-1}^{1,1}\right)+\gamma_{11}f\left(v_{i,j-1}\right) +\gamma_{12}f\left( e_{i-1,j-1}^{1,0}\right) \\ & +\gamma_{13}f\left( v_{i-1,j-1}\right) +\gamma_{14}f\left(e_{i-1,j-1}^{0,1}\right)+\gamma_{15}f\left( v_{i-1,j}\right)+\gamma_{16}f\left( e_{i-1,j}^{1,1}\right) \\ &+\gamma_{17}f\left( v_{i,j+1}\right) +\gamma_{18}f\left( e_{i,j+1}^{1,0}\right) . \end{aligned} $$

The coefficients used to define the above linear combination form the mask $\boldsymbol {\gamma }\in \mathbb {R}^{19}$, and $c\left ( u_{i,j}^{1,1}\right ) ={\mathbf {f}}^{i,j}\cdot \boldsymbol {\gamma }$, where the vector ${\mathbf {f}}^{i,j}\in \mathbb {R}^{19}$ contains the values of $f\left ( p\right )$, $p\in \mathcal {D}_{4}\cap H_{i,j}$, enumerated as indicated in Fig. 4, as well as γ. The BB-coefficients associated with the other u-points ($u_{i,j}^{1,0}$, $u_{i,j}^{0,-1}$, $u_{i,j}^{-1,-1}$, $u_{i,j}^{-1,0}$, and $u_{i,j}^{0,1}$) are defined analogously from the rotated versions of γ.

Fig. 4

Order for enumerate f ^{i, j}, α, β, γ

In the same way, $c\left ( e_{i,j}^{1,1}\right )$ and $c\left ( z_{i,j}^{1,1}\right )$ are defined by considering the masks α and β, respectively. It means $c\left ( e_{i,j}^{1,1}\right )={\mathbf {f}}^{i,j} \cdot \boldsymbol {\alpha }$ and $c\left ( z_{i,j}^{1,1}\right )={\mathbf {f}}^{i,j} \cdot \boldsymbol {\beta }$. The BB-coefficients $c\left ( e\right )$ and $c\left ( z\right )$ relative to an e-point and a z-point, respectively, are defined from the rotated versions of α and β.

It is known that a quasi-interpolation operator in $\mathcal {S}_{4}^{1}\left ( \varDelta \right )$ can reproduce the space of cubic polynomials (see e.g. [10, 15]). Therefore, the masks α, β and γ must be defined to obtain C ¹-regularity and the exactness on $\mathbb {P}_{3}$ of the quasi-interpolation operator. In other words, we require that the following constrains are satisfied:

$$\displaystyle \begin{aligned} Q_{4,2}f\in C^{1}\left( \mathbb{R}^{2}\right) \quad \text{and}\quad Q_{4,2}f=f\text{ for all }f\in\mathbb{P}_{3}. {} \end{aligned} $$

(1)

In [2] the following result is established.

Proposition 1

The imposition of (1) results in infinitely many solutions depending on the first three elements β ₁ , β ₂ , β ₃ of the mask β . The mask α is uniquely determined from the following values (see Fig. 5):

$$\displaystyle \begin{aligned} \alpha_{0} & =\alpha_{7}=-\tfrac{1}{3},\alpha_{1}=\tfrac{2}{3},\alpha _{2}=\alpha_{6}=\alpha_{8}=\alpha_{18}=\tfrac{1}{3},\alpha_{9}=\alpha _{17}=-\tfrac{1}{6},\\ \alpha_{j} & =0,\ j\in\{3,4,5,10,11,12,13,14,15,16\} \end{aligned} $$

Fig. 5

The BB-coefficient $c \left ( e_{i,j}^{1,1} \right )$ is evaluated from the mask α

The values of the masks β and γ are given in Figs. 6 and 7.

Fig. 6

The evaluation of the BB-coefficient $c \left (z_{i,j}^{1,1} \right )$ requires the mask β, whose values depend on three free parameters

Fig. 7

The mask γ needed to evaluate $c \left (u_{i,j}^{1,1} \right )$ also depends on three free parameters

Concerning the error estimates, the following classical result (see e.g. [10, 16]) holds.

Theorem 1

For an arbitrary triangle T in Δ and for a given $f\in C^{m+1}\left (\mathbb {R}^{2}\right )$, 0 ≤ m ≤ 3,

$$\displaystyle \begin{aligned}\left\Vert D^{\nu}\left( f-Q_{4,2}f\right) \right\Vert {}_{\infty,T}\leq K_{\left\vert \nu\right\vert} h^{m+1-\left\vert \nu\right\vert }\left\Vert D^{m+1}f\right\Vert {}_{\infty,\varOmega_{T}}, \end{aligned}$$

for all $0\leq \left \vert \nu \right \vert \leq m$ , ν := (ν ₁, ν ₂), where $K_{\left \vert \nu \right \vert }$ are constants independent on h and Ω _T denotes the union of all triangles T ∈ Δ that intersect T.

Masks β and γ depend on three parameters, so a strategy is needed to choose them.

The first strategy is reduced to assigning zero values to these parameters. Another possibility is to set β ₁ = β ₂ and β ₃ = 0, so that the resulting masks have certain symmetries. Since

$$\displaystyle \begin{aligned} \left\Vert Q_{4,2}\right\Vert {}_{\infty}\leq\max\left\{ \left\Vert \boldsymbol{\alpha}\right\Vert {}_{1},\left\Vert \boldsymbol{\beta}\right\Vert {}_{1},\left\Vert \boldsymbol{\gamma}\right\Vert {}_{1}\right\} \end{aligned}$$

and $\left \Vert \boldsymbol {\alpha }\right \Vert { }_{1}=3$, it is easy to minimize the upper bound $U\left ( \beta _{1}\right ) :=\max \left \{ 3,\left \Vert \boldsymbol {\beta }\right \Vert { }_{1},\left \Vert \boldsymbol {\gamma }\right \Vert { }_{1}\right \}$ to obtain that $\left \Vert Q_{4,2}\right \Vert { }_{\infty }$ is bounded by 3 if $\beta _{1}\in \left [ \frac {13}{36},\frac {41}{84}\right ]$.

In the following we will use such a choice for the free parameters, obtaining a family of quasi-interpolating splines depending on β ₁ and we denote it by $Q^{\beta _1}_{4,2}f$.

4 C ¹ Quartic Interpolating Splines on $\mathcal {D}_{1}$

In this section, we discuss the construction of new interpolating splines by application of a ‘preprocessing’ to the quasi-interpolating splines $Q^{\beta _1}_{4,2}f$. The idea is, first, to approximate the function f at the points of type e by one step of a subdivision algorithm suitable for type-1 triangulated data, and then use the quasi-interpolating operator $Q^{\beta _1}_{4,2}$. The result is a spline interpolating at the points of $\mathcal {D}_{1}$ since the quasi-interpolant $Q^{\beta _1}_{4,2}$ has this property.

4.1 The Modified Butterfly Interpolatory Subdivision Scheme

We recall that a bivariate subdivision scheme is an iterative algorithm for refining a set of points $\mathbf {f}=\{f_{\boldsymbol {j}},\ j\in \mathbb {Z}^2\}$ by repeatedly applying a linear refinement operator S _a of type

$$\displaystyle \begin{aligned} \left(S_{\mathbf{a}}\mathbf{f}\right)_{\boldsymbol{i}}=\sum_{\boldsymbol{j}\in \mathbb{Z}^2} \mathrm{a}_{\boldsymbol{i}-2\boldsymbol{j}}f_{\boldsymbol{j}}, \qquad \boldsymbol{i}\in \mathbb{Z}^2. \end{aligned} $$

(2)

From (2) we see that, at each step of the recursion, the ‘refined’ points are linear combinations of the ‘coarse’ points with real coefficients being the subdivision mask $\mathbf {a}=\left \{\mathrm {a}_{\boldsymbol {i}}, \, \boldsymbol {i}\in \mathbb {Z}^2\right \}$ (for more details, see [6, 7, 11], and reference therein). From (2) we also see that one step of a subdivision scheme transforms a set of data points attached to $\mathbb {Z}^2$ into a set of data points attached to $\frac {1}{2} \mathbb {Z}^2$.

Even though subdivision schemes usually keep refining data till convergence to a continuous limit, the idea here is to use just one step of the so called Modified Butterfly Interpolatory Subdivision Scheme (MBISS) for data on type-1 triangulations. The MBISS is an interpolatory scheme (see [13]) meaning that at each step the coarse set of points is included into the refined one and new points are inserted. This translates into the refinement rule (‘duplication’ rule)

$$\displaystyle \begin{aligned}p^{[k+1]}_{2\boldsymbol{i}}=p^{[k]}_{\boldsymbol{i}},\quad \boldsymbol{i} \in \mathbb{Z}^2. \end{aligned}$$

Each of the three insertion rules of the MBISS, transforming a sequence from level k to level k + 1, is involving 10 points lying around the point to be inserted and are exactly the same for all three possible directions of insertion. They are as follows:

• for the ‘horizontal’ insertion

  

  (3)

• for the ‘vertical’ insertion

  

  (4)

• for the ’diagonal’ insertion

  

  (5)

For the MBISS we mention the following properties that are relevant in our discussion (see [13] for all details).

Proposition 2

If $w\in \left (-\frac {1}{32},\frac {1}{32}\right )$ , then the MBISS is convergent. Moreover, for $w\in \left (-\frac {1}{32},\frac {1}{32}\right )$ the MBISS step-wise reproduces the space $\mathbb {P}_{3}$ of bivariate polynomials of degree 3. The latter means that in case the points at one level are sampled from a polynomial of degree 3, the points at the next level are samples of the same polynomial at refined grid values.

We remark that, in view of Proposition 2, the MBISS has approximation order 4 for all $\omega \in \left (-\frac {1}{32},\frac {1}{32}\right )$ and that for ω = 0 the MBISS reduces to the better known Butterfly subdivision scheme presented in [12].

4.2 C ¹ Quartic Interpolating Splines

Now we are able to construct the interpolating splines by approximating the values of f at the e-points of $Q^{\beta _1}_{4,2}f$, by one step of the MBISS. Indeed, according to (3), (4), and (5), considering the notations used for $Q^{\beta _1}_{4,2}f$, we define $f(e_{i,j}^{1,1})$ as (see Fig. 8)

$$\displaystyle \begin{aligned}\begin{array}{ll} f\left(e_{i,j}^{1,1}\right)= & \left(\frac{1}{2}-\omega\right)\left(f(v_{i,j})+f(v_{i+1,j+1})\right) + \omega\left(f(v_{i-1,j-1})+f(v_{i+2,j+2})\right) \\ & +\left(-\frac{1}{16}-\omega\right)\left(f(v_{i,j-1})+f(v_{i+2,j+1})+f(v_{i+1,j+2})+f(v_{i-1,j})\right) \\ & +\left(\frac{1}{8}+2\omega\right)\left(f(v_{i+1,j})+f(v_{i,j+1})\right) \end{array} \end{aligned}$$

and similarly for the other e-points.

Fig. 8

Edge-point stencil of MBISS, with coefficients $a_0= \frac {1}{2}-\omega$, a ₁ = ω, $a_2=- \frac {1}{16}-\omega$, $a_3= \frac {1}{8}+2\omega$

In this way, by combining the masks α, β and γ of $Q^{\beta _1}_{4,2}f$ with the masks of the MBISS, we obtain new masks α ^′, β ^′ and γ ^′ larger than the corresponding masks α, β and γ but still based on the same number of points (see Figs. 9, 10, 11). Such masks depend on the parameter β ₁, coming from the quasi-interpolating spline $Q^{\beta _1}_{4,2}f$ and ω coming from the subdivision scheme. Therefore, we denote the corresponding interpolating splines by $I_{4,1}^{\beta _1,\omega }f$.

Fig. 9

The values in this figure provide the mask α ^′ used to evaluate $c \left ( e_{i,j}^{1,1} \right )$

Fig. 10

The values in this figure provide the mask β ^′ used to evaluate $c \left ( z_{i,j}^{1,1} \right )$. The values depend on the parameter $q= \frac {3}{16}\beta _1- \frac 53\omega +4\beta _1\omega$

Fig. 11

The values in this figure provide the mask γ ^′ used to evaluate $c \left ( u_{i,j}^{1,1} \right )$. Also in this case its values depend on q

We remark that while for the construction of $Q^{\beta _1}_{4,2}f$ we assume to know the values of f on $\mathcal {D}_{2}$, for the construction of $I_{4,1}^{\beta _1,\omega }f$ it is sufficient to know the function f on $\mathcal {D}_{1}$, the vertices of the triangulation.

Thanks to the approximation properties of $Q^{\beta _1}_{4,2}$ and of the MBISS here used, we have that $I_{4,1}^{\beta _1,\omega }f$ is a quartic spline with C ¹ smoothness and the associated operator $I_{4,1}^{\beta _1,\omega }$ is exact on cubic polynomials and the error estimates of Theorem 1 hold.

Again, we continue by proposing some strategies in order to fix the free parameters. If we choose ω = 0, that corresponds to the classical Butterfly subdivision scheme, we have only one free parameter. Since

$$\displaystyle \begin{aligned}\left\|I_{4,1}^{\beta_1,\omega}\right\|{}_\infty \leq\max\left\{ \left\Vert \boldsymbol{\alpha}^\prime\right\Vert {}_{1},\left\Vert \boldsymbol{\beta}^\prime\right\Vert {}_{1}, \left\Vert \boldsymbol{\gamma}^\prime\right\Vert {}_{1}\right\} \leq \frac{145}{96}, \end{aligned}$$

we find that the value of β ₁ that minimizes the upper bound is $\beta _1=\frac {29}{72}$.

Another possibility is to consider the parameter $q:=\frac {3}{16}\beta _1-\frac 53\omega +4\beta _1\omega$, appearing in the masks β ^′ and γ ^′. If we minimize again the upper bound for the infinity norm of $I_{4,1}^{\beta _1,\omega }$ $\left (\left \|I_{4,1}^{\beta _1,\omega }\right \|{ }_\infty \leq \max \left \{ \left \Vert \boldsymbol {\alpha }^\prime \right \Vert { }_{1},\left \Vert \boldsymbol {\beta }^\prime \right \Vert { }_{1}, \left \Vert \boldsymbol {\gamma }^\prime \right \Vert { }_{1}\right \}\right )$ we find the same value $\frac {145}{96}$ obtained before, corresponding to the choice $q=\frac {29}{384}$. Hence, we can choose ω and β ₁ consequently. Another possible choice is to set $q=\frac {1}{12}$. In this case the masks β ^′ and γ ^′ have several zero coefficients in their definition, which is always convenient.

Obviously, other criteria for the selection of the free parameter can be considered.

5 Numerical Results

The performance of the operators defined in this paper are tested on two functions defined on the unit square. They are Franke’s function

$$\displaystyle \begin{aligned}\begin{array}{ll} f_{1}\left( x\right) = & 0.75e^{\left( -\frac{\left( 9x_{1}-2\right) ^{2}}{4}-\frac{\left( 9x_{2}-2\right) ^{2}}{4}\right) } +0.75e^{\left(-\frac{\left( 9x_{1}+1\right) ^{2}}{49}-\frac{9x_{2}+1}{10}\right)}\\ & +0.5e^{\left( -\frac{\left( 9x_{1}-7\right) ^{2}}{4}-\frac{\left(9x_{2}-3\right) ^{2}}{4}\right) } -0.2e^{\left( -\left( 9x_{1}-4\right)^{2}-\left( 9x_{2}-7\right) ^{2}\right) }, \end{array}\end{aligned} $$

and the radial function

$$\displaystyle \begin{aligned}f_{2}\left( x\right) =0.1\left(1+\cos\left( 12\pi\cos\left( \pi\sqrt{x_{1}^{2}+x_{2}^{2}}\right) \right) \right).\end{aligned} $$

The latter is a highly oscillating function.

In order to estimate the maximal error (ME) as a function depending on a parameter h (ME _h), the error $\left \vert f-Qf\right \vert$ is evaluated at M points in a finite subset $G=\left \{ \left ( g_{1,i},g_{2,j}\right ) :\left (i,j\right ) \in J\right \}$ $\subset \left [ 0,1\right ] ^{2}$. Moreover, the root mean square error (RMSE) is estimated as

$$\displaystyle \begin{aligned} RMSE_{h}:=\sqrt{\frac{\sum_{\left( i,j\right) \in J}\left( f\left( g_{1,i},g_{2,j}\right) -Qf\left( g_{1,i},g_{2,j}\right) \right) ^{2}}{M}}. \end{aligned}$$

Regarding the value of M, the splines Qf have been evaluated by the de Casteljau’s algorithm [16, p. 25] on 300 points in each of the triangles of the partition associated with the value h. Once computed ME _h and RSME _h, the numerical convergence orders are evaluated according to the expression $NCO:=\log _{2}\frac {ME_{h}}{ME_{h/2}}$.

As said before, f ₂ is a highly oscillating function, therefore the initial value of h must be smaller than the one used for f ₁.

Table 1 shows the values ME _h, RMSH _h and NCO _h relative to $I_{4,1}^{\beta _{1},\omega }f$ with $\beta _{1}=\frac {29}{72}$ and ω = 0. In Table 2 we report the results corresponding to the choice $q=\frac {1}{12}$.

Table 1 Numerical results relative to $I_{4,1}^{\beta _{1},\omega }f$ with $\beta _{1}= \frac {29}{72}$ and ω = 0

Table 2 Numerical results relative to $I_{4,1}^{\beta _{1},\omega }f$ with $q= \frac {1}{12}$

Finally, for the sake of comparison, in Table 3 we report the results obtained by using the quasi-interpolating spline $Q^{\beta _1}_{4,2}f$ with $\beta _{1}=\frac {2}{5} \in \left [ \frac {13}{36},\frac {41}{84}\right ]$ and in Table 4 we report the results obtained by the quasi-interpolating spline proposed in [23] (see Table 5 and Table 3 in [2]).

Table 3 Numerical results relative to $Q_{4,2}^{\beta _{1}}f$ with $\beta _{1}= \frac {2}{5}$

Table 4 Numerical results for the quasi-interpolation operator given in [23]

The results are in accordance with the theoretical order of convergence. We remark that the approximating splines $Q^{\beta _1}_{4,2}f$ and the one proposed in [23] produce results similar to those obtained by $I_{4,1}^{\beta _1,\omega }f$ for the two different selections of the parameters. However, the efficiency of $I_{4,1}^{\beta _{1},\omega }$ is higher than that of $Q_{4,2}^{\beta _{1}}$ and the operator proposed in [23] in terms of the number of evaluation points.

Moreover, Fig. 12 shows the interpolating splines $I_{4,1}^{\beta _1,\omega }f_1$, $I_{4,1}^{\beta _1,\omega }f_2$ and gives nice surfaces. They are comparable with those obtained in [2] and in [23] (see the figures there reported).

Fig. 12

The quartic C ¹ splines $I_{4,1}^{\beta _1,\omega }f_{1}$ with h = 1∕64 (left) and $I_{4,1}^{\beta _1,\omega }f_{2}$ (right) with h = 1∕256. Their masks correspond to the values provided by $\beta _{1}= \frac {29}{72}$, ω = 0

The approximation schemes here proposed have been developed to consider functions defined on the real plane, but the test functions f ₁ and f ₂ are defined on the unit square. To deal with triangles having a non interior vertex, the triangulation is extended as well as f ₁ and f ₂.

6 Conclusions

In this paper, we have constructed and analysed C ¹ quartic interpolating splines on type-1 triangulations, approximating regularly distributed data. A characteristic of the proposed methodology is that the Bernstein-Bézier coefficients in each triangle of the constructed quasi-interpolants are directly defined as appropriate linear combinations of point values at domain points that lie in a neighbourhood of the triangle to achieve C ¹ regularity and approximation order four for enough regular functions. We have constructed such interpolating splines by combining a quasi-interpolating spline with one step of an interpolatory subdivision scheme. Numerical tests confirming the theoretical results have been provided for the proposed spline scheme.

We remark that, the approximation schemes constructed in this paper and based on regularly distributed point values can be used in two-stage methods, as in [9], by firstly computing a polynomial approximant on each triangle and then by sampling the necessary data values from the approximant on each triangle. Finally, in order to apply the approximation schemes here proposed to compact domains, it is possible to construct special rules near the boundary (see [21]) or extend the triangulation.