# Completeness characterization of Type-I box splines

Nelly Villamizar, Angelos Mantzaflaris, Bert Jüttler

► To cite this version:

Nelly Villamizar, Angelos Mantzaflaris, Bert Jüttler. Completeness characterization of Type-I box splines. Geometric Challenges in Isogeometric Analysis, 49, Springer International Publishing, pp.279-304, 2022, Geometric Challenges in Isogeometric Analysis, 10.1007/978-3-030-92313-6_12. hal-02991234

HAL Id: hal-02991234

https://inria.hal.science/hal-02991234

Submitted on 5 Nov 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Completeness characterization of Type-I box splines

Nelly Villamizar, Angelos Mantzaflaris and Bert Jüttler

**Abstract** We present a completeness characterization of box splines on three-directional triangulations, also called *Type-I* box spline spaces, based on edge-contact smoothness properties. For any given Type-I box spline, of specific maximum degree and order of global smoothness, our results allow to identify the local linear subspace of polynomials spanned by the box spline translates. We use the global super-smoothness properties of box splines as well as the additional super-smoothness conditions at edges to characterize the spline space spanned by the box spline translates. Subsequently, we prove the completeness of this space space with respect to the local polynomial space induced by the box spline translates. The completeness property allows the construction of hierarchical spaces spanned by the translates of box splines for any polynomial degree on multilevel Type-I grids. We provide a basis for these hierarchical box spline spaces under explicit geometric conditions of the domain.

# 1 Introduction

*Box splines* are locally supported piecewise polynomial functions defined on uniform grids. They were first introduced by de Boor and DeVore in [11]

<footnote>Nelly Villamizar
Department of Mathematics, Swansea University, Swansea, United Kingdom
e-mail: n.y.villamizar@swansea.ac.uk</footnote>

<footnote>Angelos Mantzaflaris
Inria Sophia Antipolis-Méditerranée, Université Côte d'Azur, Nice, France
e-mail: angelos.mantzaflaris@inria.fr</footnote>

<footnote>Bert Jüttler
Johannes Kepler University Linz & RICAM, Linz, Austria
e-mail: Bert.Juettler@jku.at</footnote>
and are considered a generalization of the univariate B-spline functions to the multivariate setting. From a geometric point of view, box splines can be seen as density functions of the shadows of higher dimensional boxes and half-boxes [34]. Box splines can also be introduced as a special case of the so-called simplex splines [7]. They possess a number of useful properties that make them well-suited for applications. For instance, it has been shown that box splines have small support (a few cells of the underlying grid), they are non-negative, form a partition of unity, and are refinable i.e., the box spline spaces on refined grids are nested [3, 13].

Box splines can be defined from an arbitrary set of directional vectors in $\mathbb{R}^n$, but of particular interest for Geometric Design are box splines surfaces which are defined on uniform triangulations of the plane. In this article, we focus on *type-I box splines*. They are splines defined on three directional meshes that are commonly known as *type-I triangulations of $\mathbb{R}^2$*.

From the rich literature on box splines, we mention a few monographs and survey articles which include [1, 4, 5, 12, 13, 34], and a few representative publications on three specific topics. Firstly, a substantial number of results on the *approximation power* of box splines is described in the literature, e.g. [30, 35]. Secondly, several publications discuss techniques for the *efficient manipulation* of box spline bases. A general stable evaluation algorithm is devised in [26]. In [25] the problem of efficient evaluation of box splines is addressed by making use of the local Bernstein representation of basis functions on each triangle. Also, *numerical integration* schemes, which are important for applications, based on quasi-interpolation have been considered in [6, 29]. Recent applications of box splines include surface fitting [23], and solving linear elasticity problems in isogeometric analysis [19]. In other areas of mathematics, the theory of box splines has been proved useful to compute the volume of polytopes, and to deal with the integrate of continuous functions over polytopes [41].

In this article, we are interested in the linear spaces of spline functions generated by the translates of any fixed type-I box spline. These spline spaces share good approximation properties. For example, the set of translates of any type-I box spline form a partition of unity on $\mathbb{R}^2$, they are globally, and also locally, linearly independent. These properties of type-I box splines were studied by Dahmen and Micchelli in [10] and Jia in [20]. In particular, they investigated the linear independence of translates of a box spline in [21] and [9].

The linear independence property implies that the set of translates of any type-I box spline constitutes a basis for the spline space they span. In general this property is not satisfied for box spline functions associated to other uniform partitions, and that makes type-I box splines particularly relevant for applications. For instance, the set of translates of box splines defined from a set of four directional vectors, the so-called type-II box splines, are linearly dependent. For a concise treatment of type-II box splines, further
references, and alternative proofs of box spline properties, see [28, Chapter 12] and [4, Chapter 2].

A second interesting feature of type-I box splines is that, although for any fixed type-I box spline of degree $d$ and order of smoothness $r$, the box spline translates form a basis, in general these translates do not generate all possible piecewise polynomial functions of degree $\le d$ and global smoothness $r$ over the three-directional mesh. More precisely, the box spline translates span a proper subspace of the space of $C^r$-continuous spline functions $S_d^r(G)$ of degree at most $d$ on a three-directional mesh $G$ (cf. Figure 1), for any $d > 1$. If the domain is taken as an infinite grid $G$, or as an infinite collection of triangles in $G$, then both spaces are infinite dimensional. However, if the domain is restricted to a finite collection of triangles $\Omega$, as it is the usual setting in practice, then their finite dimension differ. Explicit dimension formulas in terms of the combinatorics of the domain $\Omega$ are well known for both spaces, dim $S_d^r(\Omega)$ can be computed using homological methods [32], or Bernstein-Bézier methods as in [4, Chapter 2].

In this work, we provide a characterization for the space spanned by box splines translates based on supersmooth conditions across the edges of the underlying partition. We prove that for any fixed degree $d$ and order of global smoothness $r$, the space of splines satisfying these extra local smoothness conditions is precisely the space spanned by the translates of the corresponding type-I box spline. From this we deduce that the type-I box spline spaces are complete with respect to the local polynomial space induced by the box spline translates. The proof of this result uses the Fourier transform of box splines, as well as the algebraic properties of the Bernstein-Bézier representations of type-I box splines. We generalise the classic definition of spline space in Definition 1 to link the spline polynomial pieces to specific polynomial subspaces of $\mathbb{R}[x, y]$, and present the main result in the paper in Section 4.

Furthermore, we apply the completeness characterization of box splines into the construction of hierarchical spline spaces based on local refinements of a type-I triangulation. Hierarchical splines constitute a well-established approach to adaptive refinement in geometric modeling [14] and numerical analysis [33, 36, 40]. Hierarchical tensor-product spline spaces were introduced by Kraft in [27] using a selection mechanism for B-splines. The method has been refined leading to spline basis with better approximation properties, such as the partition of unity property, strong stability and full approximation power [17, 18, 38, 42]. It has also been adapted to Powell-Sabin splines [37], Zwart-Powell elements and B-spline-type basis functions for cubic splines on regular grids [43]. In an earlier article, we constructed a hierarchical basis for quartic $C^2$-continuous box splines [39]. Quartic hierarchical box splines spaces have also been studied and used for surface fitting applications by Kang, Chen and Deng in [23] and [24]. Truncated hierarchical type-I box splines were considered in [22] and [19] in connection to isogeometric analysis applications. Other subdivision schemes has been explored in [15]. A $C^1$-continuous scheme based on cubic half-box splines was presented in [1].
The results we present in this article generalize our previous work [39] on quartic box splines. Our results apply to type-I box splines of any polynomial degree with no restriction on the symmetry of their support.

The remainder of this paper is organized as follows. In Section 2 we introduce the relevant notation for type-I triangulations, spline functions and the directional derivatives. Section 3 concerns the definition and properties of type-I box spline spaces. We define the space of translates and recall existing results on local and global smoothness of these functions. In Section 4 we prove Lemma 2 which is the main result in the paper, and corresponds to the edge-contact characterization for type-I box splines. In Section 5 we construct the hierarchical type-I meshes and the corresponding hierarchical box spline spaces. This construction follows the approach presented in [31] and [39]. We conclude the paper with some final remarks in Section 6.

## 2 Preliminaries

Throughout this article we assume that $G$ is the uniform type-I triangulation of the real plane $\mathbb{R}^2$, see Figure 1. This triangulation is obtained by drawing in the north-east diagonals in the bi-infinity grid with grid lines at the integers. This triangulation of the plane is associated to three directional vectors, namely $e_1 = (1, 0)$, $e_2 = (0, 1)$ and $e_3 = (1, 1)$, and therefore is also called a three directional mesh. Each line of $G$ is parallel to one of these vectors and go through the points of the integer grid $\mathbb{Z}^2$.

The collection $T$ of triangles in $G$ are considered as open sets in, and we denote by $E$ the set of all edges in $T$, and $V = \mathbb{Z}^2$ the set of vertices. The set of edges is the disjoint union $E = E_1 \cup E_2 \cup E_3$, where $E_i$ is the set of edges that are parallel to the vector $e_i$. The edges in $E_i$ are called edges of type $i$. The combinatorial closure of a triangle $\triangle \in T$, denoted by $\hat{\triangle}$, is the

<figure><img src="image_2.png" /><figcaption>**Fig. 1** Uniform type-I triangulation (or three directional mesh) of $\mathbb{R}^2$ associated to the directional vectors $e_1 = (0, 1)$, $e_2 = (0, 1)$ and $e_3 = (1, 1)$. We denote this grid as $G$.</figcaption></figure>
set consisting of the vertices and edges of $\Delta$, and $\Delta$ itself. Analogously, $\hat{\epsilon}$ of an edge $\epsilon \in E$ is the set consisting of the edge itself and its two vertices.

A multicell domain $M$ is the triangulation in $\mathbb{R}^2$ induced by a finite set of triangles $\{\Delta_1, \dots, \Delta_m\} \subset T$, i.e.

$$M = \bigcup_{i=1}^{m} \hat{\Delta}_{i}.$$

This means, that for every triangle $\Delta_i \in M$, all the vertices and edges of $\Delta_i$ are considered as elements of $M$. The subspace of $\mathbb{R}^2$ defined by the (topological) closure $\bar{\Delta}_i$ of the triangles $\Delta_i$ defining the multicell domain $M$ will be denoted by $M^*$, namely

$$(1) \qquad M^* = \bigcup_{\Delta \in M} \bar{\Delta}.$$

Given a multicell domain $M$, the diamond of an edge $\epsilon$ is defined as the union of all (at most two) triangles of $M$ which have $\epsilon$ as an edge, that is

$$\diamond(\epsilon) = \bigcup_{\Delta \in M, \epsilon \in \hat{\Delta}} \hat{\Delta}.$$

Similarly, the diamond of a vertex $\nu$ is defined by

$$\diamond(\nu) = \bigcup_{\Delta \in M, \nu \in \hat{\Delta}} \hat{\Delta},$$

which is the union of the (at most six) triangles $\Delta$ in $M$ such that $\nu$ is a vertex of $\hat{\Delta}$.

Notice that the diamond $\diamond(\cdot)$, of an edge or a vertex, depends on the multicell domain $M$. From the context, it will be clear the particular domain we are considering in each case.

We denote by $\mathbb{R}[x, y]$ the space of bivariate polynomials over the real numbers, and for $d \ge 0$, $\mathcal{P}_d \subseteq \mathbb{R}[x, y]$ is the set of all bivariate polynomials in $x$ and $y$ of total degree $\le d$. In our presentation, the polynomial pieces that define the splines are taken from a finite vector subspace $\mathcal{V}$ of $\mathbb{R}[x, y]$. This subspace $\mathcal{V}$ is not necessarily the same as $\mathcal{P}_d$ for any polynomial degree $d$, it may be a proper linear subspace. In this setting, we define the space of continuous splines $\mathbb{P}(M, \mathcal{V})$ on a multicell domain $M$ as follows.

**Definition 1** Given a multicell domain $M$, and a vector subspace $\mathcal{V} \subseteq \mathbb{R}[x, y]$, we define $\mathbb{P}(M, \mathcal{V})$ as the set of piecewise polynomials functions on $M$ i.e.,

$$\mathbb{P}(M, \mathcal{V}) = \{f \in C^0(M^*): f|_{\Delta} \in \mathcal{V}|_{\Delta} \text{ for each triangle } \Delta \in M\},$$
where $M^*$ is as defined in Equation (1), and $f|_{\Delta}$ denotes the restriction of the function $f$ to the triangle $\Delta$, and $\mathcal{V}|_{\Delta}$ is the restriction to $\Delta$ of the polynomials in $\mathcal{V}$ (seen as functions on $\mathbb{R}^2$).

In particular, when $\mathcal{V} = \mathcal{P}_d$, the space $\mathbb{P}(M, \mathcal{V})$ coincides with the usual space of $C^0$-continuous splines (or piecewise polynomial functions) on $M$ of degree at most $d$.

For any index, also called *regularity vector*, $\mathbf{s} = (s_1, s_2, s_3) \in \mathbb{Z}_{\ge 0}^3$ we consider the *mixed directional derivative operator*

$$D_s : \mathbb{R}[x, y] \to \mathbb{R}[x, y] \\ p \mapsto (\nabla \cdot \mathbf{e}_1)^{s_1} (\nabla \cdot \mathbf{e}_2)^{s_2} (\nabla \cdot \mathbf{e}_3)^{s_3} (p).$$

For a given multicell domain $M$ and a polynomial vector space $\mathcal{V}$, we extend the operator $D_s$ to elements $f \in \mathbb{P}(M, \mathcal{V})$ by applying $D_s$ to the restrictions $f|_{\Delta}$, namely

$$(D_s f)|_{\Delta} = D_s(f|_{\Delta}), \text{ for each triangle } \Delta \in M.$$

**Definition 2** For a given index set $I \subset \mathbb{Z}_{\ge 0}^3$, and a vector space of functions $\mathcal{V} \subset \mathbb{R}[x, y]$, we define the space of functions $\mathcal{D}_I(M, \mathcal{V})$ on a multicell domain $M$ by

$$\mathcal{D}_I(M, \mathcal{V}) = \{f \in \mathbb{P}(M, \mathcal{V}) : D_s f \in C^0(M^*) \text{ for all } s \in I\},$$

where $M^*$ is as defined in Equation (1).

*Remark 1* Using the notation in Definition 2 we have

$$\mathcal{D}_{\emptyset}(M, \mathcal{V}) = \mathbb{P}(M, \mathcal{V}).$$

If $S_d^r(M)$ denotes the space of globally $C^r$-continuous spline functions on $M$ of degree at most $d$, then $S_d^r(M)$ can be written as $\mathcal{D}_I(M, \mathcal{P}_d)$, where $I = \{\mathbf{s} \in \mathbb{Z}_{\ge 0}^3 : s_1 + s_2 + s_3 \le r\}$.

In this paper, for a given multicell domain $M$, we shall consider piecewise polynomial functions, or splines, on $M$ with a specific order of smoothness associated to each of the three directions associated to the grid $G$. Namely, for a regularity vector $\mathbf{d} = (d_1, d_2, d_3) \in \mathbb{Z}_{\ge 0}^3$ we define the index sets:

$$I_1^d = \{\mathbf{s} \in \mathbb{Z}_{\ge 0}^3 : s_2 + s_3 \le d_1\},$$

$$I_2^d = \{\mathbf{s} \in \mathbb{Z}_{\ge 0}^3 : s_1 + s_3 \le d_2\},$$

$$I_3^d = \{\mathbf{s} \in \mathbb{Z}_{\ge 0}^3 : s_1 + s_2 \le d_3\},$$

and consider the spline space $\mathcal{S}^d(M, \mathcal{V})$ defined as follows.
**Definition 3** For a multicell domain $M$ of the three directional grid $G$, a vector space $\mathcal{V} \subseteq \mathbb{R}[x, y]$, and a vector $\mathbf{d} \in \mathbb{Z}^3$, the spline space with edge smoothness $\mathbf{d}$ on $M$ denoted $\mathbb{S}^d(M, \mathcal{V})$ is defined as the set of piecewise polynomial functions on $M$ such that the derivatives of order $\mathbf{s} \in D_i$ are continuous across the edges of type $i$ for $i = 1, 2, 3$. More precisely,

$$ \mathbb{S}^d(M, \mathcal{V}) = \{ f \in \mathbb{P}(M, \mathcal{V}) : f|_{\diamond(\varepsilon)} \in C^{d_i} (\diamond(\varepsilon)^*) \text{ for every } \varepsilon \in E_i \cap M \\ \text{and } i \in \{1, 2, 3\} \}, $$

where $\diamond(\varepsilon)^* = \bigcup_{\varepsilon \in \hat{\Delta}, \Delta \in M} \hat{\Delta}$, see Equation (1) above.

Later in this paper (see Definition 6 below), we shall introduce a spline space but with smoothness conditions at the vertices of the domain $M$, the notation in Definition 3 will be particularly convenient for that purpose.

In the following example we illustrate Definition 3 for a specific multicell domain in the grid $G$ and a regularity vector $\mathbf{d} \in \mathbb{Z}_{\ge 0}^3$.

*Example 1* Let $M$ be the multicell domain in Figure 2. It is composed by four triangles denoted $\Delta_1, \dots, \Delta_4$, we take $\mathcal{V} = \mathcal{P}_2$ (the polynomials in $\mathbb{R}[x, y]$ of degree at most 2), and the regularity vector $\mathbf{d} = (0, 1, 0)$. Then

$$ I_1^d = \{(i, 0, 0) : i \in \mathbb{Z}_{\ge 0}\}, \quad I_2^d = \{(0, j, 0), (1, j, 0), (0, j, 1) : j \in \mathbb{Z}_{\ge 0}\}, \\ \text{and } I_3^d = \{(0, 0, k) : k \in \mathbb{Z}_{\ge 0}\}. $$

If we define $f \in \mathbb{P}(M, \mathcal{P}_2)$ by $f|_{\hat{\Delta}_i} = f_i$, where

$$ (2) \qquad \begin{aligned} f_1 &= x^2; & f_3 &= (y - 2x)(y - 2); \\ f_2 &= (x - y + 1)^2; & f_4 &= 2(x - 1)(y - x) + 2x - y^2. \end{aligned} $$

Then $f$ is an element in $\mathbb{S}^d(M, \mathcal{P}_2)$. In fact, if we put $g_{1,2} = (f_1, f_2) = f|_{\diamond(\varepsilon_1)}$, since $f_1 - f_2 = (y - 1)(2x - y + 1)$ then $D_s g_{1,2}$ is a continuous function on $\diamond(\varepsilon_1)$ for $\mathbf{s} \in I_1^d$. Similarly, if we put $g_{i,i+1} = (f_i, f_{i+1})$ it is easy to check that $D_s g_{2,3}$ and $D_t g_{3,4}$ are continuous functions for every $\mathbf{s} \in I_2^d$ and $\mathbf{t} \in I_3^d$ on $\diamond(\varepsilon_2)$ and $\diamond(\varepsilon_3)$, respectively. $\diamond$

In an analogous way as we defined a spline space associated to smoothness along the edges (Definition 3) of a multicell domain, we will introduce a space of splines with additional smoothness at the vertices of a given multivariate domain $M$. We prepare this definition by listing the possible vertex-vertex contact configurations $\bar{\Delta} \cap \bar{\Delta}' = \{\nu\}$ between any pair of triangles $\Delta, \Delta' \in T$. First we need the following definitions.

**Definition 4** Two triangles $\Delta$ and $\Delta'$ in the grid $G$, are said to be *edge-connected* if there is a collection of triangles $\Delta_0, \Delta_1, \dots, \Delta_m \in T$ such that $\Delta = \Delta_0, \Delta' = \Delta_m$ and $\bar{\Delta}_{i-1} \cap \bar{\Delta}_i \in E$ for every $i = 1, \dots, m$. Such a collection of triangles $\Delta_0, \Delta_1, \dots, \Delta_m$ is called an *edge-connected chain* between $\Delta$ and $\Delta'$.
<figure><img src="image_3.png" /><figcaption>Fig. 2 Multicell domain $M = \cup_{i=1}^{4} \hat{\Delta}_i$, with edges $\varepsilon_i = \bar{\Delta}_i \cap \bar{\Delta}_{i+1}$ for $i = 1, 2, 3$.</figcaption></figure>

**Definition 5** If $\Delta, \Delta' \in T$ are triangles such that $\bar{\Delta} \cap \bar{\Delta}' \neq \emptyset$, we define the smoothness type $\text{ST}(\Delta, \Delta') \subseteq \{1, 2, 3\}$ as the set of edge-types that are in the shortest edge-connected chain in $G$ between $\Delta$ and $\Delta'$. If $\Delta = \Delta'$ we define $\text{ST}(\Delta, \Delta') = \emptyset$.

For any given pair of triangles $\Delta, \Delta' \in T$ with a non-empty intersection, we can identify them with a pair of triangles from $A$ to $F$ in Figure 3, and their smoothness type $\text{ST}(\Delta, \Delta')$ becomes one of the subsets listed in the table on the left of Figure 3.

<table><thead><tr><th>ST(Δ, Δ')</th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th></tr></thead><tbody><tr><th>A</th><td>Ø</td><td>{1}</td><td>{1,2}</td><td>{1,2,3}</td><td>{2,3}</td><td>{3}</td></tr><tr><th>B</th><td>{1}</td><td>Ø</td><td>{2}</td><td>{2,3}</td><td>{1,2,3}</td><td>{1,3}</td></tr><tr><th>C</th><td>{1,2}</td><td>{2}</td><td>Ø</td><td>{3}</td><td>{1,3}</td><td>{1,2,3}</td></tr><tr><th>D</th><td>{1,2,3}</td><td>{2,3}</td><td>{3}</td><td>Ø</td><td>{1}</td><td>{1,2}</td></tr><tr><th>E</th><td>{2,3}</td><td>{1,2,3}</td><td>{1,3}</td><td>{1}</td><td>Ø</td><td>{2}</td></tr><tr><th>F</th><td>{3}</td><td>{1,3}</td><td>{1,2,3}</td><td>{1,2}</td><td>{2}</td><td>Ø</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 3 Smoothness types of a pair of triangles $\Delta, \Delta'$ such that $\Delta \cap \Delta' \neq \emptyset$. We can identify $\Delta, \Delta'$ with two triangles in the picture on the right. The type $\text{ST}(\Delta, \Delta')$ is the corresponding index set shown in the table on the left side, which is constructed according to the shortest edge-connected chain between them (see Definition 4).</figcaption></figure>

We now use Definitions 4 and 5 to introduce the space of *strongly regular splines* associated to a multicell domain $M$ in the three directional grid $G$.

**Definition 6** For a multicell domain $M \subset T$, a vector space $V \subseteq \mathbb{R}[x, y]$, and a regularity vector $d = (d_1, d_2, d_3)$, a spline $f \in \mathbb{P}(M, V)$ is said to be *strongly regular* if for any pair of triangles $\Delta, \Delta' \in M$ such that $\Delta \cap \Delta' \neq \emptyset$, for every triple of indexes associated to the smoothness type $\text{ST}(\Delta, \Delta')$ the derivatives of $f$ are $C^0$-smooth. (Notice that the edge-connected chain are composed by triangles in the grid $G$ and are not necessarily in $M$.) The set of all strongly regular splines on $M$ will be denoted as $\hat{S}^d(M, V)$, it is given by
$$ \hat{S}^d(M, \mathcal{V}) = \left\{ f \in \mathbb{P}(M, \mathcal{V}) : f|_{U} \in \mathbb{D}_I(U, \mathcal{V}) \text{ for } \Delta, \Delta' \in M, \Delta \cap \Delta' \neq \emptyset, \right. \\ \left. U = \bar{\Delta} \cup \bar{\Delta}', \text{ and } I = \bigcap_{i \in \text{ST}(\Delta, \Delta')} I_i^d \right\}. $$

The set $\hat{S}^d(M, \mathcal{V})$ is the linear space of splines with edge and vertex smoothness $d$ on the multicell domain $M$.

**Example 2** Let $M$ be the multicell domain in Figure 2, $\mathcal{V} = \mathcal{P}_2$ and $d = (0, 1, 0)$ as in Example 1. It is easy to check that the piecewise function $f$ defined in Equation (2) is in $\hat{S}^d(M, \mathcal{V})$. For instance, if we take the triangles $\Delta_1$ and $\Delta_4$, the smoothness type $\text{ST}(\Delta_1, \Delta_4) = \{1, 2, 3\}$. Then $I = \bigcap_{i=1}^3 I_i^d = \{(0, 0, 0)\}$, and in fact $f_1(1, 1) = f_4(1, 1)$. Similarly, taking the triangles $\Delta_2$ and $\Delta_3$, we get $\text{ST}(\Delta_2, \Delta_4) = \{2, 3\}$ and $I = \bigcap_{i=2}^3 I_i^d = \{(0, 0, k) : k = 0, 1\}$. The polynomials $f_2$ and $f_4$ and also their derivatives $\partial(f_i)/\partial(x-y)$, for $i=2$ and $3$, have the same value at $(1, 1)$.

In contrast, if $g$ is the function on $M$ defined by $g|_{\Delta_i} = g_i$ with $g_1 = 0$, $g_2 = y-1$, $g_3 = x^2-2x+y$ and $g_4 = x^2-y$, then $g$ is also in $\hat{S}^d(M, \mathcal{V})$, but it is not in $\hat{S}^d(M, \mathcal{V})$. In fact, for the triangles $\Delta_2$ and $\Delta_4$, the derivatives $\partial g_2/\partial(x-y) = -1$ and $\partial g_4/\partial(x-y) = 2x+1$. Then $g|_U \notin \mathbb{D}_I(U, \mathcal{V})$ for $U = \bar{\Delta}_2 \cup \bar{\Delta}_4$. $\diamond$

**Remark 2** From Definitions 3 and 6, it is clear that both $\hat{S}^d(M, \mathcal{V})$ and $\mathcal{S}^d(M, \mathcal{V})$ are contained in the space of splines that are globally $C^r$-continuous on $M$, where $r = \min\{d_1, d_2, d_3\}$. Moreover, they are both contained in $\mathbb{D}_I(M, \mathcal{V})$ for $I = I_1^d \cap I_2^d \cap I_3^d$ (see Definition 2), and $\hat{S}^d(M, \mathcal{V}) \subseteq \mathcal{S}^d(M, \mathcal{V})$. By Example 2 we also know that the set of strongly regular splines $\hat{S}^d(M, \mathcal{V})$ may be properly contained in the spline space $\mathcal{S}^d(M, \mathcal{V})$.

In the following we give a sufficient condition for the equality $\mathcal{S}^d(M, \mathcal{V}) = \hat{S}^d(M, \mathcal{V})$. For this we introduce the concept of over concave vertices and kissing triangles.

**Definition 7** For a multicell domain $M$ in the three-directional grid $G$ we say that a vertex $\nu \in V$ on the boundary of $M$ is over-concave if $\text{star}(\nu) \setminus M$ consists of a single triangle, where $\text{star}(\nu) = \bigcup_{\nu \in \bar{\Delta}} \bar{\Delta}$.

Since we work exclusively in the three directional grid $G$ then star($\nu$) consists of 6 triangles, 6 edges and $v$ itself, see Figure 4.

**Definition 8** Two triangles $\Delta$ and $\Delta'$ in $M$ such that $\Delta \cap \Delta' = \{v\}$ is a vertex $v \in V$ will be called *kissing triangles*.

In Figure 3, for instance, the triangles $\{A, E\}$, $\{A, D\}$, $\{A, C\}$ are kissing triangles.
<figure><img src="image_5.png" /><figcaption>Fig. 4 The vertex $\nu$ on the boundary of $M$ is an over-concave vertex as in Definition 7.</figcaption></figure>

**Proposition 1** If $M$ be a multicell domain in the three directional grid $G$, such that it does not have kissing triangles nor over-concave boundary vertices, then $\mathbb{S}^d(M, \mathcal{V}) = \hat{\mathbb{S}}^d(M, \mathcal{V})$ i.e., all splines with edge smoothness $d$ on $M$ are strongly regular.

*Proof* The statements follows directly from Definitions 3, 6 and 7. □

### 3 Box splines on type-I triangulations

In this section we define box splines on the uniform type-I triangulation $G$ defined in Section 2, Figure 1. This triangulation has vertices at all lattice points $(i, j) \in \mathbb{Z}^2$.

**Definition 9** If $\beta$ is a real-valued function on $\mathbb{R}^2$, we denote by supp $(\beta)$ the support $\beta$, and it is defined as the set of points $x \in \mathbb{R}^2$ such that $\beta(x) \neq 0$.

Recall from Definition 7, that the star of a vertex $\nu \in V$, denoted star $(\nu)$, is defined by

$$ \text{star}(\nu) = \bigcup_{\Delta \in T, \nu \in \hat{\Delta}} \hat{\Delta}. $$

It is the multicell domain composed by all the triangles $\Delta \in T$ which have $\nu$ as one of their vertices, together with the edges and vertices of these triangles.

**Definition 10** If $n = (n_1, n_2, n_3) \in \mathbb{Z}^3$ is a triple of integers such that $n_i \ge 1$, the type-I box spline $\mathcal{B}_n$ associated to $n$ is defined recursively by

$$ \mathcal{B}_n(x) = \int_0^1 \mathcal{B}_{n-e_i}(x - t e_i) dt, $$

for $x \in \mathbb{R}^2$ and $i \in \{1, 2, 3\}$ such that $n - e_i \ge 1 = (1, 1, 1)$; the function $\mathcal{B}_1$ is the classical *Courant hat function* with support on the star of the vertex $(1, 1)$ given in Figure 5. More precisely, $\mathcal{B}_1$ is the piecewise linear function on $\mathbb{R}^2$ satisfying $\mathcal{B}_1(1, 1) = 1$ and $\mathcal{B}_1(i, j) = 0$ for $(i, j) = (0, 0), (0, 1), (1, 2), (2, 1)$ and $(2, 2)$.
<figure><img src="image_6.png" /><figcaption>Fig. 5 Support of the Courant hat function $\mathcal{B}_1$, it corresponds to star $(\nu)$ where $\nu$ is the vertex (1, 1) (left), support of the box splines $\mathcal{B}_{(2,1,1)}$ (center) and $\mathcal{B}_{(2,2,1)}$ (right).</figcaption></figure>

The coordinates $n_i$ of $n$ denote the number of convolutions of $\mathcal{B}_1$ along the directions $e_i$. The support of the box spline $\mathcal{B}_n$ is the zonotope in $\mathbb{R}^2$ formed by the Minkowski sum of the direction vectors $e_i$ taken $n_i$ times, for $i = 1, 2, 3$, respectively (see Figure 5 for an example). Moreover, for every $n$, the box spline $\mathcal{B}_n$ is strictly positive for all $x$ in the interior of its support, and zero otherwise [28, Theorem 12.2].

From the general theory of type-I box splines, it follows that the box spline $\mathcal{B}_n$ is independent of the order in which of the vectors $e_i$ appear in the recursive construction of $\mathcal{B}_n$ in Definition 10. This result follows immediately from the formula for the Fourier transform of a type-I box spline [28, Theorem 12.6].

For any $n$, the box spline $\mathcal{B}_n$ is a piecewise polynomial function on three directional triangulation $G$, and each polynomial is of total degree $n = |n|-2$, where $|n| = n_1 + n_2 + n_3$. It is also well-known that $\mathcal{B}_n$ is a $C^r$-continuous function on $\mathbb{R}^2$, where $r = \min_{i=1,2,3}\{|n| - n_i - 2\}$ [28, Theorem 2.4].

There is a rich literature on type-I box splines, a detailed construction and the proof of structural and smoothness properties can be found for instance in [28, Chapter 12] or [12]. In particular, it is known that each convolution along a direction $e_i$ increases the continuity of the box spline with respect to differentiation in that direction by one [28, Theorem 12.3]. Thus, following the notation introduced in Section 2, $d = (n_2+n_3-2, n_1+n_3-2, n_1+n_2-2)$ then

$$ (3) \qquad \mathcal{B}_n \in \mathbb{S}^d(G, \mathcal{P}_n). $$

We denote by $B_n(G)$ the set of integer translates of the box spline $\mathcal{B}_n$, which is defined as the set

$$ (4) \qquad B_n(G) = \{\mathcal{B}_n(\cdot - v) : v \in \mathbb{Z}^2\}. $$

The set $B_n(G)$ is also called the set of shifted box splines associated to the direction vector $n$.

*Remark 3* Notice that translates in $B_n(G)$ have distinct support, it is the zonotope which is the support of $\mathcal{B}_n$ shifted by $v$. In fact, the set $B_n(G)$ is
(globally) linearly independent [28, Theorem 12.19] i.e., if

$$ \sum_{v \in \mathbb{Z}^2} a_v \mathcal{B}_n(x - v) = 0, \text{ for all } x \in \mathbb{R}^2 $$

then $a_v = 0$ for all $v \in \mathbb{Z}^2$. Furthermore, it has been shown that the translates in $B_n(G)$ are also locally linearly independent i.e., if $A$ is an open set, then the shifted box splines

$$ \{ \mathcal{B}_n(\cdot - v) : \text{supp}(\mathcal{B}_n(\cdot - v)) \cap A \neq \emptyset \} $$

are linearly independent [8, 21]. Here, $\text{supp}(\beta)$ denotes the support of the function $\beta$ (Definition 9).

We now introduce the definition of the set of active box splines on a given multicell domain $M$ in the type-I triangulation $G$.

**Definition 11** If $M \subseteq G$ is a multicell domain, we define

$$ \text{Supp}_n(M) = \{ v \in \mathbb{Z}^2 : \text{supp}(\mathcal{B}_n(\cdot - v)) \cap M^* \neq \emptyset \}, $$

and the set of active box splines $\mathcal{B}_n$ on $M$ by

$$ B_n(M) = \{ \mathcal{B}_n(\cdot - v) \mid_{M} : v \in \text{Supp}_n(M) \}, $$

where $M^*$ is the closure of $M$ in $\mathbb{R}^2$ as defined in Equation (1).

In particular, if the multicell domain $M = \hat{\Delta}$, for a triangle $\Delta \in T$, then $B_n(\hat{\Delta})$ is the set of translates $\mathcal{B}_n(\cdot - v) \in B_n(G)$ whose support contains $\Delta$. The number of elements in $B_n(\hat{\Delta})$ is given by

$$ (5) \qquad \phi(\boldsymbol{n}) = n_1 n_2 + n_1 n_3 + n_2 n_3, $$

where $\boldsymbol{n} = (n_1, n_2, n_3)$.

**Definition 12** If $\mathcal{B}_n(\cdot - v)$ is the translate of the type-I box spline $\mathcal{B}_n$ by $v \in \mathbb{Z}^2$, then we take $(1, 1) - v$ as the point of reference of $\text{supp}(\mathcal{B}_2(\cdot - v))$ in the lattice. For a triangle $\Delta \in T$, we define the 1-ring neighbourhood of $\Delta$ as the set of reference lattice points $(1, 1) - v$ such that $\sup(\mathcal{B}_n(\cdot - v)) \cap \Delta \neq \emptyset$.

For instance, if $\mathbf{2} = (2, 2, 2)$ then the elements in $B_2(\hat{\Delta})$ are the translates $\mathcal{B}_2(\cdot - v)$ associated to the $\phi(\boldsymbol{n}) = 12$ lattice points in a 1-ring neighbourhood of $\Delta$ in the grid $G$, which are shown in Figure 6.

Notice that to any type-I box spline $\mathcal{B}_n$ and a triangle if $\Delta \in T$ we can associate a linear space of polynomials. Namely, extending by linearity, we can take $\mathcal{V}_n|_{\Delta}$ as the space generated by the restriction of the active box splines $\mathcal{B}_n$ to the triangle $\Delta$ i.e.,

$$ (6) \qquad \mathcal{V}_n|_{\Delta} = \text{span} B_n(\hat{\Delta}) . $$
<figure><img src="image_7.png" /><figcaption>**Fig. 6** The 12 lattice points correspond to the 1-ring of a triangle $\Delta \in T$ associated to the box spline $\mathcal{B}_2 = \mathcal{B}_{(2,2,2)}$. Each of these points is the reference point $(1, 1) - \mathbf{v}$ for the translate $\mathcal{B}_2(\cdot - \mathbf{v})$ such that $\Delta \subseteq \text{supp}(\mathcal{B}_2(\cdot - \mathbf{v}))$.</figcaption></figure>

By Equations (6) and (3), we see that $V_n|_{\Delta}$ is a linear subspace of $P_n \subseteq \mathbb{R}[x, y]$, for any $\Delta \in T$ and $n = n_1 + n_2 + n_3 - 2$.

We now prove that for any $n \in \mathbb{Z}^3$, the subspace $V_n|_{\Delta} \subseteq P_n$ is independent of the choice of the triangle $\Delta \in T$. The proof of this result is a generalization of [39, Proposition 27], where we consider the case $\mathbf{2} = (2, 2, 2)$ and the box spline $\mathcal{B}_2$.

**Proposition 2** Let $n = (n_1, n_2, n_3) \in \mathbb{Z}^3_{\ge 1}$ and $f \in P_n$, with $n = n_1 + n_2 + n_3 - 2$. Then, $V_n|_{\Delta} = V_n|_{\Delta'}$ for any pair of triangles $\Delta$ and $\Delta'$ in $T$.

**Proof** Let $\Delta$ and $\Delta'$ be two triangles in the three-directional grid $G$. Denote by $G^0$ the triangulation of $\mathbb{R}^2$ obtained by the lines parallel to the vectors $e'_1 = (a, 0)$, $e'_2 = (0, a)$ and $e'_1 = (a, a)$, for a fixed number $a \in \mathbb{Z}$. Notice that for any $a \in \mathbb{Z}$, we can see the grid $G$ as a refinement of a grid $G^0$. Denote by $\Delta_a$ the triangle in $G^0$ with vertices at $(0, 0)$, $(0, a)$ and $(a, a)$. In particular, let us take $\ell \in \mathbb{Z}_+$ and $a = 2^\ell$ in such a way that the translate $\tilde{\Delta} = \Delta_a - \mathbf{v}$ of $\Delta_a$ by a vector $\mathbf{v} \in \mathbb{Z}^2$ contains both $\Delta$ and $\Delta'$. Then, $B_n(1/2^\ell \cdot)$ is the correspondent box spline associated to $n$ in the grid $G^0$. By the refinement equation for box splines [28, Theorem 12.9], there exists a finite sequence $\{c_v\}_{v \in \mathbb{Z}^2}$ such that

$$ (7) \qquad B_n(1/2^\ell \cdot) = \sum_{v \in \mathbb{Z}^2} c_v B_n(\cdot - v). $$

Let us denote by $V_n^0|_{\tilde{\Delta}}$ the span of the box spline translates $B_n(1/2^\ell \cdot - \mathbf{v})$ restricted to $\tilde{\Delta}$ in $G^0$. By the symmetry of the box splines supports, the number $\phi(n)$ of active translates on a triangle is independent of the grid and of the given triangle in the grid. Furthermore, these translates are linearly independent (see Remark 3). Thus,

$$ (8) \qquad \dim V_n^0|_{\tilde{\Delta}} = \dim V_n|_{\Delta} = \dim V_n|_{\Delta'}. $$
Taking the restrictions to $\Delta$ and $\Delta'$, Equation (7) implies $(V_n^0|_{\bar{\Delta}})|_{\Delta} \subseteq V_n|_{\Delta}$ and $(V_n^0|_{\bar{\Delta}})|_{\Delta'} \subseteq V_n|_{\Delta'}$.

Since $V_n^0|_{\bar{\Delta}}$ is a polynomial subspace of $\mathcal{P}_n$, we have $V_n^0|_{\bar{\Delta}} = (V_n^0|_{\bar{\Delta}})|_{\Delta} = (V_n^0|_{\bar{\Delta}})|_{\Delta'}$. In particular, both $(V_n^0|_{\bar{\Delta}})|_{\Delta}$ and $(V_n^0|_{\bar{\Delta}})|_{\Delta'}$ have the same dimension as $V_n^0|_{\bar{\Delta}}$. The statement follows by applying Equation (8). $\square$

Proposition 2 implies that for a given $n \in \mathbb{Z}_{\ge 1}^3$ the restrictions of the translates of the box spline $\mathcal{B}_n$ to a triangle $\Delta \in T$ define a polynomial space which is independent of $\Delta$. From now on, we will denote such polynomial space as $V_n$.

Remark 4 For any $\Delta \in T$ an $n \in \mathbb{Z}_{\ge 1}^3$, Remark 3 implies that $B_n(\hat{\Delta}) \subseteq \mathcal{P}_n$ is a linearly independent set. Here $\mathcal{P}_n$ is as before, the set of bivariate polynomials of degree at most $n = n_1 + n_2 + n_3 - 2$, and $n = (n_1, n_2, n_3)$. The number of elements in $B_n(\hat{\Delta}) = \phi(n)$ (Equation (5)) is the dimension of the space of polynomials $\dim V_n$ associated to the type-I box $\mathcal{B}_n$. Thus, $\dim(V_n) = n_1n_2 + n_1n_3 + n_2n_3 \le \binom{n_1+n_2+n_3}{2} = \dim \mathcal{P}_n$.

For $n_i \ge 1$, equality holds only for $n = \mathbf{1} = (1, 1, 1)$, which corresponds to polynomial space $V_1$ associated to the Courant hat function $\mathcal{B}_1$ in Definition 10. For any other $n \in \mathbb{Z}^3$ and the corresponding box spline $\mathcal{B}_n$, the polynomial space $V_n$ is a proper subspace of $\mathcal{P}_n$.

# 4 Characterization of box spline spaces

Let $\Delta \in T$, $n \in \mathbb{Z}_{\ge 1}^3$, and consider $V_n = \operatorname{span} B_n(\hat{\Delta})$. As observed in Remark 4, the set $B_n(\hat{\Delta})$ of the box spline translates with support on $\Delta$ is linearly independent, and hence the restriction of a polynomial $f \in V_n$ to $\Delta$ has a unique representation

$$ (9) \qquad f|_{\Delta}(\boldsymbol{x}) = \sum_{\beta \in B_n(\hat{\Delta})} \lambda_{\Delta}^{\beta}(f|_{\Delta})\beta(\boldsymbol{x}), \quad \boldsymbol{x} \in \bar{\Delta}, $$

for coefficients $\lambda_{\Delta}^{\beta}(f|_{\Delta}) \in \mathbb{R}$.

**Lemma 1** Let $n = (n_1, n_2, n_3) \in \mathbb{Z}_{\ge 1}^3$, $f$ and $f'$ in $V_n$, and $M = \hat{\Delta} \cup \Delta'$, such that $\Delta, \Delta' \in T$ and $\bar{\Delta} \cap \Delta' \in E_i$ for some $i \in \{1, 2, 3\}$.

If $(f|_{\Delta}, f'|_{\Delta'}) \in \mathbb{S}^d(M, V_n)$, then there exist polynomials $g, h \in V_n$ such that

$$ (10) \qquad (f|_{\Delta}, f'|_{\Delta'}) = (g|_{\Delta}, f'|_{\Delta'}) + (h|_{\Delta}, 0|_{\Delta'}), $$

with $\lambda_{\Delta}^{\beta}(g|_{\Delta}) = \lambda_{\Delta'}^{\beta}(f'|_{\Delta'})$ for every $\beta \in B_n(\hat{\Delta}) \cap B_n(\hat{\Delta'})$.
**Proof** Define

$$g|_{\Delta} = \sum_{\beta \in B(\hat{\Delta}) \cap B(\hat{\Delta}')} \lambda_{\Delta}^{\beta}(f'|_{\Delta})\beta|_{\Delta} + \sum_{\beta \in B(\hat{\Delta}) \setminus B(\hat{\Delta}')} 0 \cdot \beta|_{\Delta}.$$

Then $g|_{\Delta} \in \mathcal{V}_n|_{\Delta}$, and extending by linearity we can see $g|_{\Delta}$ as the restriction to $\Delta$ of a polynomial $g$ in $\mathcal{V}_n \subseteq \mathbb{R}[x, y]$. By construction, the pair $(g|_{\Delta}, f'|_{\Delta'})$ satisfies the required condition, and taking $h = f - g$ we obtain Equation (10). $\square$

**Lemma 2** Let $\mathbf{n} = (n_1, n_2, n_3) \in \mathbb{Z}_{\ge 1}^3$, $f$ and $f'$ in $\mathcal{V}_n$, and $\Delta, \Delta' \in T$, such that $\bar{\Delta} \cap \bar{\Delta}' \in E_i$ for some $i \in \{1, 2, 3\}$. Then, for $M = \hat{\Delta} \cup \hat{\Delta}'$ the following two statements are equivalent:

(i) The pair $(f|_{\Delta}, f'|_{\Delta'}) \in \mathbb{S}^d(M, \mathcal{V}_n)$, with $\mathbf{d} = (n_2+n_3-2, n_1+n_3-2, n_1+n_2-2)$.

(ii) For every $\beta \in B_n(\hat{\Delta}) \cap B_n(\hat{\Delta}')$, it holds $\lambda_{\Delta}^{\beta}(f|_{\Delta}) = \lambda_{\Delta', f'|_{\Delta'}}^{\beta}$.

**Proof** (ii) $\Rightarrow$ (i) Let $(f, f') \in \mathcal{V}_n$ be a pair of polynomials satisfying (ii). Then

$$(11) \quad (f|_{\Delta}, f'|_{\Delta'}) = \sum_{\beta \in B_n(M)} \lambda_{\Delta}^{\beta}(f|_{\Delta})\beta|_{\Delta \cup \Delta'} + (h|_{\Delta}, 0|_{\Delta}) + (0|_{\Delta}, h'|_{\Delta'}),$$

where

$$h|_{\Delta} = \sum_{\beta \in B_n(\hat{\Delta}) \setminus B_n(\hat{\Delta}')} \lambda_{\Delta}^{\beta}(f|_{\Delta})\beta|_{\Delta}, \quad \text{and} \quad h'|_{\Delta'} = \sum_{\beta \in B_n(\hat{\Delta}') \setminus B_n(\hat{\Delta})} \lambda_{\Delta'}^{\beta}(f'|_{\Delta'})\beta|_{\Delta}.$$

Since $\beta \in \mathbb{S}^d(M, \mathcal{V}_n)$ for every $\beta \in B_n(M)$, then the first term in Equation (11) is in $\mathbb{S}^d(M, \mathcal{V}_n)$. Now, if $\beta \in B(\hat{\Delta}) \setminus B(\hat{\Delta}')$ then $(\beta|_{\Delta}, 0|_{\Delta'}) = \beta|_M$, and similarly for $\beta \in B(\hat{\Delta}') \setminus B(\hat{\Delta})$. Hence, the last two terms in Equation (11) are also in $\mathbb{S}^d(M, \mathcal{V}_n)$, and (i) follows.

(i) $\Rightarrow$ (ii) By Lemma 1 it is enough to consider $(f|_{\Delta}, 0|_{\Delta'}) \in \mathbb{S}^d(M, \mathcal{V}_n)$. We need to show that $\lambda_{\Delta}^{\beta}(f|_{\Delta}) = 0$ for every $\beta \in B(\hat{\Delta}) \cap B(\hat{\Delta}')$. To simplify, by an abuse of notation we will denote $\text{Supp}_n(\hat{\Delta}) \cap \text{Supp}_n(\hat{\Delta}')$ simply by $\text{Supp}_n(\hat{\varepsilon}_3)$.

Let $\bar{\Delta} \cap \bar{\Delta}' = \varepsilon_i \in E_i$, and denote by $b_i$ the barycentric coordinate relative to $\Delta$ which vanishes at the edge $\varepsilon_i$. Let $n = n_1+n_2+n_3$. Then $(f|_{\Delta}, 0|_{\Delta'}) \in \mathbb{S}^d(M, \mathcal{V}_n)$ if and only if the polynomial $b_i^{n-n_i-1}$ divides $f$, see [2, Lemma 2.2]. Notice that the latter condition is satisfied if and only if the Bernstein-Bézier coefficients $c_{jkl}$ of $f|_{\Delta}$ are zero for every $0 \le j \le n - n_1 - 2$.

Without loss of generality we can assume that $i = 3$ and $\Delta$ is the triangle with vertices at $(0, 0)$, $(1, 0)$, and $(1, 1)$. Thus, $b_3 = x-y$. We will prove that if
$f \in \mathcal{V}_n$ and $b_3^{n-n_3-1}$ divides $f$ then $\lambda_{\Delta}^{\beta}(f|_{\Delta}) = 0$ for every $\beta \in B(\hat{\Delta}) \cap B(\hat{\Delta}')$. We proceed by induction on $n$, with $n_i \ge 1$.

The induction base is $n=3$, with $\mathbf{n}=(1,1,1)$, $n_3=1$ and $n-n_3-1=1$. We have

$$B_n(\hat{\Delta} \cup \hat{\Delta}') = \{\beta_j\}_{j=0}^3,$$

with $\beta_0 = \mathcal{B}_n$, and $\beta_i = \mathcal{B}_n(\cdot + e_i)$ for $i=1,2,3$. Thus, the only translates with support on $\Delta$ are $\beta_0, \beta_2$ and $\beta_3$. Since $\beta_0 = b_1, \beta_2 = b_3$, and $\beta_3 = b_2$, then

$$f|_{\Delta} = \lambda_{\Delta}^{\beta_0}(f|_{\Delta})b_1|_{\Delta} + \lambda_{\Delta}^{\beta_2}(f|_{\Delta})b_3|_{\Delta} + \lambda_{\Delta}^{\beta_3}(f|_{\Delta})b_2|_{\Delta}.$$

Since the polynomials $b_1, b_2, b_3$ are linearly independent, and by hypothesis $b_1|f$, it follows $\lambda_{\Delta}^{\beta_i}(f|_{\Delta}) = 0$ for $i=2,3$. This proves the statement for the case $n=3$.

Let us assume that the result is true for every $m \le n$ for some $n \ge 3$. Let $\mathbf{n} = (n_1, n_2, n_3)$ with $n+1 = n_1 + n_2 + n_3$. We consider three cases, in the first two cases only one of the indices $n_i$ is $\ge 2$ and in the last case at least two of the indexes are $\ge 2$.

**Case 1.** Suppose $n_1 \ge 2$, and $n_2 = n_3 = 1$.

We have $(x-y)^{n_1}|f$ and $D_{e_1}f \equiv 0 \mod (x-y)^{n_1-1}$. Notice that Equation (9) may be rewritten as

$$(12) \qquad f|_{\Delta} = \sum_{v \in \mathbb{Z}^2} \lambda_v(f) \mathcal{B}_n(\cdot - v)|_{\Delta},$$

where $\lambda_v = 0$ for every $v \notin \text{Supp}_n(\Delta)$, and $\lambda_v(f) = \lambda_{\Delta}^{\beta}(f|_{\Delta})$ for $\beta \in B(\hat{\Delta})$ and $\beta = \mathcal{B}_n(\cdot - v)$.

Moreover, we know that for any linear combination of box splines

$$\begin{align} D_{e_i} \sum_{v \in \mathbb{Z}^2} a_v \mathcal{B}_n(\cdot - v) &= \sum_{v \in \mathbb{Z}^2} a_v (\mathcal{B}_m(\cdot - v) - \mathcal{B}_m(\cdot - v - e_1)) \tag{13} \\ &= \sum_{v \in \mathbb{Z}^2} (a_{v+e_i} - a_v) \mathcal{B}_m(\cdot - v + e_i), \end{align}$$

for $a_v \in \mathbb{R}$ for every $v \in \mathbb{Z}^2$, and $\mathbf{m} = (n_1 - 1, n_2, n_3)$, see [28, Lemma 12.3].

Thus,

$$\begin{align*} D_{e_1} \sum_{v \in \mathbb{Z}^2} \lambda_v(f) \mathcal{B}_n(\cdot - v)|_{\Delta} &= \sum_{v \in \mathbb{Z}^2} (\lambda_{v+e_1}(f) - \lambda_v(f)) \mathcal{B}_m(\cdot - v + e_1)|_{\Delta} \\ &\equiv 0 \mod (x-y)^{n_1-1}, \end{align*}$$
where $\mathbf{m} = (n_1 - 1, 1, 1)$. By induction hypothesis $\lambda_{\mathbf{v}+\mathbf{e}_1}(f) = \lambda_{\mathbf{v}}(f)$ for every $\mathbf{v} \in \text{Supp}_{\mathbf{m}}(\hat{\varepsilon}_3)$.

Notice that, since $\mathbf{n} = (n_1, 1, 1)$ then the elements $\mathbf{v} \in \text{Supp}_{\mathbf{v}}(\hat{\Delta})$ are either a multiple $te_1$ of $e_1$ or of the form $e_2 + te_1$, for $t \in \mathbb{Z}$. Thus, we have

$$f|_{\Delta} = \lambda_{e_1}(f) \sum_{t \in \mathbb{Z}} \mathcal{B}_n(\cdot - te_1)|_{\Delta} + \lambda_{e_2}(f) \sum_{t \in \mathbb{Z}} \mathcal{B}_n(\cdot - e_2 + te_1)|_{\Delta},$$

for constants $\lambda_{e_i}(f) \in \mathbb{R}$, for $i = 1, 2$. Moreover, $\mathcal{B}_n(\cdot - te_1)|_{\hat{\varepsilon}_1} = 0$ for every $t$. In particular, they are zero at the vertex $(0,0)$. But $f(0,0) = 0$, and

$$1 = \sum_{\mathbf{v} \in \mathbb{Z}^2} \mathcal{B}_n(\cdot - \mathbf{v}) = \sum_{t \in \mathbb{Z}} \mathcal{B}_n(\cdot - t\mathbf{e}_1) + \mathcal{B}_n(\cdot - e_2 + t\mathbf{e}_1).$$

Then $f|_{(0,0)} = \lambda_{e_2}(f) \sum_{t \in \mathbb{Z}} \mathcal{B}_n(\cdot - e_2 + te_1)|_{(0,0)} = \lambda_{e_2}(f) = 0$. We obtain $\lambda_{e_1}(f) = 0$ by considering the restriction at the vertex $(1, 1)$.

**Case 2.** Suppose $n_3 \ge 2$ and $n_1 = n_2 = 1$.

By hypothesis $(x-y)|f$, and so $D_{e_3}f \equiv 0 \mod (x-y)$. Following the same argument as above, $\lambda_{\mathbf{v}+\mathbf{e}_3}(f) = \lambda_{\mathbf{v}}(f)$ for every $\mathbf{v} \in \text{Supp}_{\mathbf{n}}(\hat{\varepsilon}_3)$. Thus, there is a constant $\lambda_{e_3}$ which is equal to $\lambda_{\mathbf{v}}(f)$ for every $\mathbf{v} \in \text{Supp}_{\mathbf{n}}(\hat{\varepsilon}_3)$, and

$$f|_{\varepsilon_3} = \lambda_{e_3}(f) \sum_{\mathbf{v} \in \mathbb{Z}^2} \mathcal{B}_n(\cdot - \mathbf{v})|_{\varepsilon_3}.$$

Since $f|_{\varepsilon_3} = 0$, and $\sum_{\mathbf{v} \in \mathbb{Z}^2} \mathcal{B}_n(\cdot - \mathbf{v})|_{\varepsilon_3} = 1$, it follows $\lambda_{e_3}(f) = 0$.

**Case 3.** At least two of the indices $n_i$ are $\ge 2$, say $n_1, n_2 \ge 2$. By hypothesis $(x-y)^{n_1+n_2-1}|f$, and so $D_{e_i}f \equiv 0 \mod (x-y)^{n_1+n_2-2}$ for $i = 1, 2$. Similarly as before, rewrite $f|_{\Delta}$ as in Equation (12), and consider Equation (13) with $i = 1$. Thus,

$$D_{e_1} \sum_{\mathbf{v} \in \mathbb{Z}^2} \lambda_{\mathbf{v}}(f) \mathcal{B}_n(\cdot - \mathbf{v})|_{\Delta} = \sum_{\mathbf{v} \in \mathbb{Z}^2} (\lambda_{\mathbf{v}+\mathbf{e}_1}(f) - \lambda_{\mathbf{v}}(f)) \mathcal{B}_m(\cdot - \mathbf{v} + \mathbf{e}_1)|_{\Delta} \\ \equiv 0 \mod (x-y)^{n_1+n_2-2}.$$

By induction hypothesis $\lambda_{\mathbf{v}+\mathbf{e}_1}(f) = \lambda_{\mathbf{v}}(f)$ for every $\mathbf{v} \in \text{Supp}_{\mathbf{m}}(\hat{\varepsilon}_3)$. Similarly, by considering $D_{e_2}f$ we get $\lambda_{\mathbf{v}+\mathbf{e}_2}(f) = \lambda_{\mathbf{v}}(f)$ for every $\mathbf{v} \in \text{Supp}_{\mathbf{m}'}(\hat{\varepsilon}_3)$, where $\mathbf{m}' = (n_1, n_2-1, n_3)$. This implies that the coefficients $\lambda_{\mathbf{v}}(f)$ are equal to a constant $\lambda$, for every $\mathbf{v} \in \text{Supp}_{\mathbf{n}}(\hat{\varepsilon}_3)$.

Therefore, $f|_{\varepsilon_3} = \lambda \sum_{\mathbf{v} \in \mathbb{Z}^2} \mathcal{B}_n(\cdot - \mathbf{v})|_{\varepsilon_3}$. But $f|_{\varepsilon_3} = 0$, and $\sum_{\mathbf{v} \in \mathbb{Z}^2} \mathcal{B}_n(\cdot - \mathbf{v}) = 1$, in particular when taking the restriction to $\varepsilon_3$. Hence, $0 = \lambda = \lambda_{\Delta}^{\beta}(f)$, for every $\beta \in B(\hat{\Delta}) \cap B(\hat{\Delta}')$.

An analogous proof applies when the edge of intersection between $\bar{\Delta}$ and $\bar{\Delta}'$ is parallel to one of the other two vectors $e_1$ or $e_2$. $\square$
The edge-contact property plays a fundamental role for the construction of hierarchical spline spaces, we present that construction for any type-I box spline in Section 5. The following examples illustrate that importance of the properties of type-I box splines used to prove Lemma 2, we show that not every spline space possesses those properties.

*Example 3* Let $M = \hat{\Delta} \cup \hat{\Delta}'$ be the multicell domain in Figure 7.

<figure><img src="image_8.png" /><figcaption>**Fig. 7** The triangles $\Delta$ and $\Delta'$ in $G$ define the multicell domain $M$ in Example 3, the triangles share the edge $\varepsilon \in E_2$ that is parallel to the directional vector $e_2$.</figcaption></figure>

Take the set $B = \{f_1, \dots, f_4\}$ of spline functions $f_i$ on $M$ defined as

$$f_1 = (y^2 + 3x^2 + 4x, y^2 + x), \quad f_2 = (4y^2, 4y^2), \\ f_3 = (x^2, 0), \quad \text{and} \quad f_4 = (0, x^2).$$

Each pair of polynomials $f_i$ is defined on $\Delta$ and $\Delta'$, respectively. Then, $B$ is contained in the space of splines $S^0(M, Q)$, where $0 = (0, 0, 0)$, and $Q \subseteq P_2$ is the linear subspace of polynomial spanned by $x$, $x^2$, and $y^2$.

We have

$$Q|_{\Delta} = B|_{\Delta} = \{y^2 + 3x^2 + 4x, 4y^2, x^2\}|_{\Delta}, \quad \text{and} \\ Q|_{\Delta'} = B|_{\Delta'} = \{y^2 + x, 4y^2, x^2\}|_{\Delta'}.$$

Then, $g = (5 \cdot (y^2 + 3x^2 + 4x) + 4y^2, y^2 + x + 2 \cdot (4y^2)) \in S^0(M, Q)$, but $g$ is not an element in span $(B)$. $\diamond$

The following example illustrates the importance of the spline space $S^d(M, \mathcal{V}_n)$ (Definition 3) in the proof of Lemma 2.

*Example 4* Let $M = \hat{\Delta} \cup \hat{\Delta}'$ be the multicell domain defined from the triangles $\Delta$ and $\Delta'$ such that $\Delta \cap \Delta' = \varepsilon \in E_3$ in Figure 8. Take $\mathbf{n} = (2, 1, 1)$, and consider the linear space $\mathcal{V}_n = \text{span } B_n(\hat{\Delta})$. The support and Bernstein coefficients of the box spline $B_{(2,1,1)}$ are displayed in Figure 8. The generators of $\mathcal{V}_{(2,1,1)}$ can easily be described by restricting the translates $B_{(2,1,1)}(\cdot - \mathbf{v}) \in B_n(M)$ to $\Delta'$ and using the Bernstein coefficients of $B_{(2,1,1)}$. Namely, $\mathcal{V}_{(2,1,1)}$ is generated by

$$f_1 = 2(x - y)y + y^2; \quad f_2 = 2(1 - x)y + y^2;$$
$$f_3 = (x - y)^2 ;$$

$$f_4 = (1 - x)^2 + 4(1 - x)(x - y) + (x - y)^2 + 2(1 - x)y + 2(x - y)y ;$$

and $f_5 = (1 - x)^2 .$

In particular,

$$f = 4(x - y)y + 4(1 - x)(x - y) + (x - y)^2 = f_1 - f_2 + f_4 - f_5 \in \mathcal{V}_{(2,1,1)} .$$

Let us notice that $g = (0|_{\Delta}, f|_{\Delta'}) \in \mathbb{S}^0(M, \mathcal{V}_n)$, but $g \notin \text{span} \mathcal{B}_n(M)$. In fact, for $\beta(\cdot) = \mathcal{B}_n(\cdot)$ we have $\beta|_{\Delta'} = f_1$, and $\lambda_{\Delta'}^{\beta}(f|_{\Delta'}) = 1$, but $\lambda_{\Delta}^{\beta}(0|_{\Delta}) = 0$.

On the other hand, $\varepsilon \in E_3$ i.e., $\varepsilon$ is an edge parallel to the directional vector $e_3$, and $g$ is not a $C^1$-continuous spline on $M$. Thus, $g \notin \mathbb{S}^d(M, \mathcal{V}_n)$ for $d = (0, 1, 1)$. $\diamond$

<figure><img src="image_9.png" /><figcaption>Fig. 8 Bernstein coefficients of the box spline $2\mathcal{B}_{(2,1,1)}$.</figcaption></figure>

**Definition 13** A multicell domain $M$ is *admissible* with respect to a type-I box spline $\mathcal{B}_n$ if the support of any $\beta \in \mathcal{B}_n(M)$ is a connected set, and there exist no over-concave vertices (Definition 7), and no kissing triangles in $M$ (Definition 8).

In view of Lemma 2 we arrive to the following completeness result.

**Corollary 1 (Completeness of type-I box splines)** If $M \subseteq G$ is an admissible domain, and $\mathbf{n} = (n_1, n_2, n_3) \in \mathbb{Z}^3_{\ge 1}$, then the generating set $\mathcal{B}_n(M)$ is complete for $\mathbb{S}^{d(\mathbf{n})}(M, \mathcal{V}_n)$, where $d(\mathbf{n}) = (n_2 + n_3 - 2, n_1 + n_3 - 2, n_1 + n_2 - 2)$.

## 5 Hierarchical type-I box splines

In this section, to any given box spline $\mathcal{B}_n$ we associate a space of *special splines* defined on a hierarchical grid. We construct a hierarchical basis for
such space and prove that this basis is complete under certain assumptions on the domain hierarchy.

For an integer $N \ge 0$, we recursively define a sequence of three-directional grids $G^1, G^2, \dots, G^N$ as follows. We take $G^1 = G$ as the three-directional grid with vertices $\mathbb{Z}^2$ introduced in Section 2, Figure 1. The hierarchical grids

$$G^\ell \text{ for } \ell = 2, \dots, N$$

are defined recursively, in such a way that $G^{\ell+1}$ is obtained from $G^\ell$ by one global, uniform dyadic refinement step. More precisely, the grid $G^{\ell+1} = \frac{1}{2}G^\ell$ is the triangulation of $\mathbb{R}^2$ with vertices at points $1/2^\ell(k, k)$, obtained by drawing in the lines $x = k/2^\ell$, $y = k/2^\ell$, and $x - y = k/2^\ell$, for all $k \in \mathbb{Z}$. Thus, to construct $G^{\ell+1}$, every triangle in the grid $G^\ell$ is split into four smaller ones, as illustrated in Figure 9. The index $\ell$ will be called the *level* of the grid, and the number $N$ specifies the number thereof. Each grid $G^\ell$ is a uniform three-directional grid, similarly as for the grid $G = G^1$ before, we consider the triangles in this grid as open sets in $\mathbb{R}^2$.

<figure><img src="image_10.png" /><figcaption>Fig. 9 Three levels of three-directional hierarchical grids.</figcaption></figure>

Let $\Omega$ be a domain of $\mathbb{R}^2$ whose boundary $\partial\Omega$ is the union of edges from the grid $G^N$. We define a hierarchical multicell domain $H$ associated to the domain $\Omega$ as follows.

A *nested sequence of subdomains* of $\Omega$ is defined as a collection of domains $\mathcal{M}^\ell$ such that

$$\emptyset = \mathcal{M}^0 \subseteq \mathcal{M}^1 \subseteq \dots \subseteq \mathcal{M}^N = \Omega,$$

where $\mathcal{M}^\ell = \bigcup_{\Delta \in \mathcal{M}^\ell} \bar{\Delta}$, and $\mathcal{M}^\ell \subseteq G^\ell$ is a multicell domain in the grid $G^\ell$, for each $\ell = 1, \dots, N$.

Thus, for each level $\ell$, the boundary $\partial \mathcal{M}^\ell$ is a union of edges of the grid $G^\ell$. The difference between two successive subdomains, denoted $\mathcal{D}^\ell$, is defined as the closure

$$\mathcal{D}^\ell = \overline{\mathcal{M}^\ell \setminus \mathcal{M}^{\ell-1}}.$$

The associated refined domain of level $D^\ell \subseteq G^\ell$ is defined as $D^\ell = T^\ell(\mathcal{D}^\ell)$, where $T^\ell(\cdot)$ is the triangulation operator which restrict the grid $G^\ell$ to a given subset of the plane $\mathbb{R}^2$. More precisely,
$$T^{\ell}(\mathcal{Q}) = \{\hat{\Delta} \in G^{\ell} : \Delta \subset \mathcal{Q}\}.$$

The hierarchical multicell domain $H$ associated to $\Omega$ is then the collection of triangles form all levels of the refinement area

$$H = \bigcup_{\ell=1}^{N} D^{\ell}.$$

Using this notation, the domain $\Omega$ can be written as the union $\Omega = \bigcup_{\Delta \in H} \bar{\Delta}$.

**Definition 14** Let $H$ be a three-directional hierarchical multicell domain associated to a domain $\Omega \subseteq \mathbb{R}^2$, and let $\mathcal{B}_n$ be a box spline, for some triple $n = (n_1, n_2, n_3) \in \mathbb{Z}_{\ge 1}^3$. We define $\mathbb{P}(H, \mathcal{V}_n)$ as the set of piecewise polynomial functions on $H$ associated to $\mathcal{B}_n$ i.e.,

$$\mathbb{P}(H, \mathcal{V}_n) = \{f \in C^0(\Omega) : f|_{\Delta} \in \mathcal{V}_n|_{\Delta} \text{ for each triangle } \Delta \in H\}.$$

If $d = (n_2 + n_3 - 2, n_1 + n_3 - 2, n_1 + n_2 - 2)$, the hierarchical box spline space with edge smoothness $d$ on $H$ is defined as the set

$$(14) \quad \mathbb{S}^d(H, \mathcal{V}_n) = \{f \in \mathbb{P}(H, \mathcal{V}_n) : f|_{\diamond(\varepsilon)} \in C^{d_i} (\diamond(\varepsilon)^*) \text{ for every } \varepsilon \in E_i \cap H \text{ and } i \in \{1, 2, 3\}\}.$$

For $d$ as above, we define the linear space of hierarchical box splines with edge and vertex smoothness $d$ on the hierarchical multicell domain $H$ as the set

$$(15) \quad \hat{\mathbb{S}}^d(H, \mathcal{V}_n) = \left\{ \begin{array}{l} f \in \mathbb{P}(H, \mathcal{V}_n) : f|_U \in \mathbb{D}_I(U, \mathcal{V}_n) \text{ for } \Delta, \Delta' \in M^\ell, \\ \text{for some } \ell, \Delta \cap \Delta' \neq \emptyset, U = \bar{\Delta} \cup \bar{\Delta}', \text{ and } I = \bigcap_{i \in \text{ST}(\Delta, \Delta')} I_i^d \end{array} \right\}.$$

In Equation (14), the diamond of and edge $\varepsilon \in H$ is taken over the multicell domain $M^\ell$ such that $\varepsilon$ is an edge of the a triangle $\Delta \in M^\ell$. Namely,

$$\diamond(\varepsilon) = \bigcup_{\Delta \in M^\ell, \varepsilon \in \hat{\Delta}} \hat{\Delta}.$$

Let us fix $n = (n_1, n_2, n_3) \in \mathbb{Z}_{\ge 1}^3$ and the corresponding box spline $\mathcal{B}_n$.

For each level $\ell = 1, \dots, N$ we denote by $B_n^\ell$ the set of translates of $\mathcal{B}_n$ with respect to the grid $G^\ell$. In particular, we have $B_n^1 = B_n(G)$ as defined in Equation (4), and recursively

$$B_n^{\ell+1} = \{\beta(2^\ell) : \beta \in B_n^\ell\}.$$
In an analogous way as we introduce $B_n(M)$ in Definition 11 for a multicell domain $M$ in the three-directional grid $G$, we now define the set $B_n^\ell(M^\ell)$ of active box splines on the multicell domain $M^\ell$ in $G^\ell$ as follows,

$$B_n^\ell(M^\ell) = \{\beta|_{M^\ell}: \beta \in B_n^\ell, \text{ and } \text{supp } \beta \cap \mathcal{M}^\ell \neq \emptyset\}.$$

A set of linearly independent box splines on a hierarchical multicell domain $H$ can be constructed by a selection procedure analogous to that proposed by Kraft in [27] in the context of tensor-product B-splines.

For all levels $\ell$, we select box splines translates, and define the sets $K^\ell$ as follows

$$K^\ell = \{\beta^\ell \in B_n^\ell(M^\ell): \text{supp } \beta^\ell \cap \mathcal{M}^{\ell-1} = \emptyset\}.$$

The collection of these box splines translates in the levels $\ell = 1, \dots, N$ forms a hierarchical box splines basis given by

$$(16) \qquad K = \bigcup_{\ell=1}^{N} K^{\ell}.$$

The linear independence of the functions in $K$ is implied by the local linear independence of the box splines at each level, see [27].

Then the question of completeness of hierarchical type-I box spline spaces can be stated as follows. For a given hierarchical multicell domain $H$, does the basis $K$ in Equation (16) span the hierarchical box spline space $S^d(H, \mathcal{V}_n)$ defined in Equation (14)? Does $K$ span $\hat{S}^d(H, \mathcal{V}_n)$ defined in Equation (15)?

In the following theorem we address the first question, and provide a sufficient condition for the completeness of the hierarchical spline basis.

**Theorem 1** Let $H$ be a three-directional hierarchical multicell domain, and let $B_n$ be a box spline, for some triple $n = (n_1, n_2, n_3) \in \mathbb{Z}_{\ge 1}^3$. The basis $K$ in Equation (16) spans the hierarchical box spline space $S^d(H, \mathcal{V}_n)$ if each multicell domain $M^\ell$ of $H$ is admissible (Definition 13) with respect to the grid level $\ell$.

*Proof* The proof follows standard arguments already presented in [16, 31] for the case of hierarchical tensor B-spline bases. Let $\Omega \subset \mathbb{R}^2$ be the domain associated to $H$. We prove by induction on the levels $\ell$ that every spline function $s \in S^d(H, \mathcal{V}_n)$ admits a representation

$$(17) \qquad s = (h^1 + \dots + h^N)|_{\Omega},$$

where $h^\ell \in \text{span } B_n^\ell(M^\ell)$, and

$$(18) \qquad h^\ell|_{\mathcal{M}^\ell} = s|_{\mathcal{M}^\ell} - (h^1 + \dots + h^{\ell-1})|_{\mathcal{M}^\ell}.$$

for $\ell = 1, \dots, N$.

For any given level $\ell$, all functions $h^k|_{\mathcal{M}^\ell}$ of lower levels $k < \ell$ are contained in $S^d(M^\ell, \mathcal{V}_n)$. This follows from the relation
$$ \mathrm{span} B_n^k(M^k)|_{M^\ell} \subseteq \mathbb{S}^d(M^\ell, \mathcal{V}_n). $$

It follows that $s|_{M^\ell} \in \mathbb{S}^d(M^\ell, \mathcal{V}_n)$. Consequently, the right-hand side of Equation (18) is contained in $\mathbb{S}^d(M^\ell, \mathcal{V}_n)$. Since the multicell domain $M^\ell$ is admissible, we conclude that $h^\ell \in \mathrm{span} B_n^\ell(M^\ell)$ according to Corollary 1. In particular, choosing $\ell = N$ in Equation (18) we get Equation (17).

Moreover, the construction of the functions $h^\ell$ ensures that

$$ h^\ell|_{M^{\ell-1}} = 0|_{M^{\ell-1}}. $$

Since the box splines possess the property of local linear independence we can conclude that $h^\ell \in \mathrm{span} K^\ell$. This completes the proof. $\square$

Theorem 1 is a consequence of Corollary 1, and therefore of Lemma 2. This result generalizes the completeness property of the space of translates of the quartic box spline $B_2$ proved in [39, Theorem 26].

## 6 Concluding remarks

*Remark 5* The contact characterization property proved in Lemma 2 implies the completeness of the space spanned by the translates of type-I box splines $B_n$ on a multicell domain $M$, with respect to the spline space $\mathbb{S}^{d(n)}(M, \mathcal{V}_n)$, where $d(n) = (n_2+n_3-2, n_1+n_3-2, n_1+n_2-2)$, and $n = (n_1, n_2, n_3)$. This result holds whenever $M$ is an admissible domain i.e., whenever $M$ does not have over-concave vertices nor kissing triangles, and $\mathrm{supp}(\beta)$ is connected for all translates $\beta$ of $B_n$ which have support on $M$. This is a sufficient condition, but it will also be interesting to prove necessary conditions to achieve this completeness property of the type-I box spline space. In this direction, a complete characterization of the vertex-vertex contact plays a crucial role. This calls for exploring the algebraic formulation of super-smoothness at vertices in order to proving an analogous to Lemma 2 for vertex-vertex contact of type-I box splines.

*Remark 6* We partially undertake the vertex-vertex contact question raised in the previous remark, for low degrees. In particular, we have verified algorithmically the vertex-vertex contact (that is, Lemma 2 for the case $\bar{\Delta} \cap \Delta' \in V$ and the space $\hat{\mathbb{S}}^d(M, \mathcal{V}_n)$) for all type-I box splines up to $n = (4, 4, 4)$.

The approach is based on the fact that both statements (i) and (ii) of Lemma 2 yield linear relations on the coefficients $\lambda_\Delta^\beta(f|\Delta)$ and $\lambda_{\Delta'}^\beta(f'|\Delta')$. We can express each of the two statements as matrices $A^{(i)}$ and $A^{(ii)}$. The latter matrix has the form

$$ (19) \qquad A^{(ii)} = [I_p \mathbf{0}_q - P I_p \mathbf{0}_q], $$
where $P$ is a permutation matrix, $p = \#B_n(\hat{\Delta}) \cap B_n(\hat{\Delta}')$, and $q = \phi(n) - p$.

The matrix<fnref n="1" /> $A^{(i)}$ can be computed as a product $A^{(i)} = C_v L_M$. The factor $C_v$ describes the Bézier continuity conditions at the common vertex $v$, corresponding to the smoothness type ST($\Delta$, $\Delta'$) (Definition 5) and to the regularity vector $d = (n_2+n_3-2, n_1+n_3-2, n_1+n_2-2)$. The right factor $L_M$ is the Bernstein-Bézier representation of the translates of $B_n$, considered independently on each of the two triangles of $M$:

$$ (20) \qquad L_M = \begin{bmatrix} L_{\Delta} & 0 \\ 0 & L_{\Delta'} \end{bmatrix} $$

or, equivalently, a change of basis matrix of the space $C^{-1}(M^*)$.

Showing that Lemma 2 holds in this setting (and for a fixed $n$) is done by showing that $A^{(i)}$ and $A^{(ii)}$ are equivalent matrices. Indeed, in all our computations we obtain $A^{(ii)}$ as the reduced row echelon form of $A^{(i)}$ for type-I box splines up to total degree 12. This verifies that the matrices are equivalent and so the vertex-vertex contact lemma holds in these cases.

**Remark 7** In the discussion of completeness of hierarchical type-I box splines spaces there are two main differences to the original approach, which was formulated for tensor-product splines.

First, the translates of a box spline do not span the whole space of bivariate polynomials of a given total degree. For this reason, this special polynomial subspace had to be identified. In some sense this situation generalizes the tensor-product case, where the B-splines span a polynomial space of a given (coordinate-wise) bi-degree, instead of the space of bivariate polynomials of a given total degree.

Second, the constraints on the domains are entirely different, due to the differences in the characterization of contacts between polynomial pieces. For bivariate tensor-product splines, both edge-edge and vertex-vertex contacts could be characterized easily by the equality of spline coefficients. In the case of type-I box splines, we proved the characterization solely for edge-edge contacts. Consequently, the completeness of hierarchical splines requires more severe restrictions to the hierarchical grid.

We have alleviated these extra restrictions by proving algorithmically the vertex-vertex contact for small polynomial degrees (total degree up to 12). By proving a characterization of the vertex-vertex contact of box splines for arbitrary degree, as we indicated in Remark 5, we could relax these restrictions on the hierarchical grids and construct more general hierarchical type-I spline space. We leave this as a future research direction.

<footnote n="1">¹ Observe that $\ker A^{(i)} = \hat{S}^d(M, \mathcal{V}_n)$.</footnote>
References

[1] P. Barendrecht, M. Sabin, and J. Kosinka, *A bivariate C¹ subdivision scheme based on cubic half-box splines*, Comput. Aided Geom. Design **71** (2019), 77–89.

[2] L. Billera, *Homology of smooth splines: generic triangulations and a conjecture of Strang*, Trans. Amer. Math. Soc. **310** (1988), no. 1, 325–340.

[3] W. Böhm, *Subdividing multivariate splines*, Comput.-Aided Des. **15** (1983), no. 6, 345–352.

[4] C. Chui, *Multivariate splines*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 54, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1988. With an appendix by Harvey Diamond.

[5] M. Dæhlen and T. Lyche, *Box splines and applications*, Geometric modeling, 1991, pp. 35–93.

[6] C. Dagnino, P. Lamberti, and S. Remogna, *Numerical integration based on trivariate C² quartic spline quasi-interpolants*, BIT Numer. Math. **53** (2013), no. 4, 873–896 (English).

[7] W. Dahmen and C. Micchelli, *Recent progress in multivariate splines*, Approximation theory, IV (College Station, Tex., 1983), 1983, pp. 27–121. MR754343

[8] —, *Line average algorithm: A method for the computer generation of smooth surfaces*, Computer Aided Geometric Design **2** (1985), no. 1, 77–85.

[9] —, *On the local linear independence of translates of a box spline*, Studia Math. **82** (1985), no. 3, 243–263. MR825481

[10] —, *On the solution of certain systems of partial difference equations and linear dependence of translates of box splines*, Trans. Amer. Math. Soc. **292** (1985), no. 1, 305–320. MR805964

[11] C. de Boor and R. DeVore, *Approximation by smooth multivariate splines*, Trans. Amer. Math. Soc. **276** (1983), no. 2, 775–788.

[12] C. de Boor, K. Höllig, and S. Riemenschneider, *Box splines*, Applied Mathematical Sciences, vol. 98, Springer-Verlag, New York, 1993.

[13] C. de Boor and A. Ron, *Box splines revisited: Convergence and acceleration methods for the subdivision and the cascade algorithms*, J. Approx. Theory **150** (2008), no. 1, 1–23.

[14] D. Forsey and R. Bartels, *Hierarchical B-spline refinement*, Comput. Graph. **22** (1988), 205–212.

[15] C. Gérot, *Elementary factorisation of box spline subdivision*, Adv. Comput. Math. **45** (2019), no. 1, 153–171.

[16] C. Giannelli and B. Jüttler, *Bases and dimensions of bivariate hierarchical tensor-product splines*, J. Comput. Appl. Math. **239** (2013), 162–178.

[17] C. Giannelli, B. Jüttler, and H. Speleers, *THB-splines: The truncated basis for hierarchical splines*, Comput. Aided Geom. Des. **29** (2012), 485–498.
[18] __________, *Strongly stable bases for adaptively refined multilevel spline spaces*, Adv. Comput. Math. **40** (2014), no. 2, 459–490.

[19] C. Giannelli, T. Kanduč, F. Pelosi, and H. Speleers, *An immersed-isogeometric model: application to linear elasticity and implementation with THBox-splines*, J. Comput. Appl. Math. **349** (2019), 410–423.

[20] R. Jia, *Linear independence of translates of a box spline*, Journal of Approximation Theory **40** (1984), no. 2, 158–160.

[21] __________, *Local linear independence of the translates of a box spline*, Constr. Approx. **1** (1985), no. 2, 175–182. MR891538

[22] T. Kanduč, C. Giannelli, F. Pelosi, and H. Speleers, *Adaptive isogeometric analysis with hierarchical box splines*, Comput. Methods Appl. Mech. Engrg. **316** (2017), 817–838.

[23] H. Kang, F. Chen, and J. Deng, *Hierarchical B-splines on regular triangular partitions*, Graph. Models **76** (2014), no. 5, 289–300.

[24] __________, *Hierarchical box splines*, 14th international conference on computer-aided design and computer graphics (cad/graphics), 2015, pp. 73–80.

[25] M. Kim and J. Peters, *Fast and stable evaluation of box-splines via the BB-form*, Numer. Algorithms **50** (2009), no. 4, 381–399 (English).

[26] L. Kobbelt, *Stable evaluation of box-splines*, Numer. Algorithms **14** (1997), no. 4, 377–382 (English).

[27] R. Kraft, *Adaptive und linear unabhängige Multilevel B-Splines und ihre Anwendungen*, Ph.D. Thesis, 1998.

[28] M. Lai and L. L. Schumaker, *Spline functions on triangulations*, Encyclopedia of Mathematics and its Applications, vol. 110, Cambridge University Press, 2007.

[29] P. Lamberti, *Numerical integration based on bivariate quadratic spline quasi-interpolants on bounded domains*, BIT Numer. Math. **49** (2009), no. 3, 565–588 (English).

[30] T. Lyche, C. Manni, and P. Sablonnière, *Quasi-interpolation projectors for box splines*, J. Comput. Appl. Math. **221** (2008), no. 2, 416–429.

[31] D. Mokriš, B. Jüttler, and C. Giannelli, *On the completeness of hierarchical tensor-product B-splines*, J. Comput. Appl. Math. **271** (2014), 53–70.

[32] B. Mourrain and N. Villamizar, *Homological techniques for the analysis of the dimensions of triangular splines spaces*, Chapter 1 of this thesis. (2012).

[33] M. Mustahsan, *Finite element methods with hierarchical WEB-splines*, Ph.D. Thesis, 2011.

[34] H. Prautzsch and W. Boehm, *Box splines*, Handbook of computer aided geometric design, 2002, pp. 255–282.

[35] A. Ron and N. Sivakumar, *The approximation order of box spline spaces*, Proc. Amer. Math. Soc. **117** (1993), no. 2, 473–482.

[36] D. Schillinger, L. Dedè, M.A. Scott, J.A. Evans, M.J. Borden, E. Rank, and T.J.R. Hughes, *An isogeometric design-through-analysis methodology based on adaptive hierarchical refinement of NURBS, immersed boundary methods, and T-spline CAD surfaces*, Comp. Meth. Appl. Mech. Engrg. **249-252** (2012), 116–150.

[37] H. Speleers, P. Dierckx, and S. Vandewalle, *Quasi-hierarchical Powell-Sabin B-splines*, Comput. Aided Geom. Des. **26** (2009), 174–191.

[38] Hendrik Speleers and Carla Manni, *Effortless quasi-interpolation in hierarchical spaces*, Numer. Math. (2015), 1–30 (English).

[39] N. Villamizar, A. Mantzaflaris, and B. Jüttler, *Characterization of bivariate hierarchical quartic box splines on a three-directional grid*, Computer Aided Geometric Design **41** (2016), 47–61.

[40] A.-V. Vuong, C. Giannelli, B. Jüttler, and B. Simeon, *A hierarchical approach to adaptive local refinement in isogeometric analysis*, Comp. Meth. Appl. Mech. Engrg. **200** (2011), 3554–3567.

[41] Z. Xu, *Multivariate splines and polytopes*, J. Approx. Theory **163** (2011), no. 3, 377–387. MR2771249
[42] C. Zeng, F. Deng, X. Li, and J. Deng, *Dimensions of biquadratic and bicubic spline spaces over hierarchical T-meshes*, J. Comput. Appl. Math. **287** (2015), 162–178.

[43] U. Zore and B. Jüttler, *Adaptively refined multilevel spline spaces from generating systems*, Comput. Aided Geom. Des. **31** (2014), no. 7–8, 545–566.