Dominique Schmitt
email: dominique.schmitt@uha.fr

Bivariate B-splines from convex configurations

Keywords: B-spline, Simplex spline, Convex pseudo-circles

An order-k univariate spline is a function defined over a set S of at least k + 2 real parameters, called knots. Such a spline can be obtained as a linear combination of B-splines, each of them being defined over a subset of k + 2 consecutive knots of S, called a configuration of S.

In the bivariate setting, knots are pairs of reals and B-splines are defined over configurations of k + 3 knots.

Using convex pseudo-circles, we define a family of configurations that gives rise to bivariate B-splines that retain the fundamental properties of univariate B-splines. We also give an algorithm to construct such configurations.

Introduction

Splines have been introduced by Schoenberg in the forties. Since then, they have been extensively used, in particular in the context of curve modeling. A spline is a piecewise polynomial function defined over a set of knots.

In the univariate case, knots are reals. Given a set S of n reals and an integer 0 ≤ k ≤ n -2, an order-k spline over S can be written as a linear combination of order-k base splines, called B-splines. Each order-k B-spline is a piecewise degree-k polynomial defined over a subset of k + 2 consecutive knots of S (see Figure 1). t0 t1 t2 t3 t4 t5 t6 surfaces, one needs to extend both the definition of B-spline and the notion of "subset of consecutive knots of S", also called configurations of S. Different such generalizations have been proposed but Neamtu observed in 2001 that none preserves all fundamental properties of univariate splines [START_REF] Neamtu | What is the natural generalization of univariate splines to higher dimensions?[END_REF]. One of these properties, called the polynomial reproduction property, states that the univariate spline space spanned by order-k B-splines contains all degree-k polynomials. This property is necessary for a spline space to have optimal approximation properties [START_REF] De Boor | Topics in multivariate approximation theory[END_REF][START_REF] Dahmen | Recent progress in multivariate splines[END_REF]. Therefore, Neamtu proposed a new extension of univariate splines that satisfies this fundamental property [START_REF] Neamtu | Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay[END_REF]. First, B-splines are generalized using the simplex splines introduced by de Boor [START_REF] De Boor | Splines as linear combinations of B-splines. a survey[END_REF], where an order-k simplex spline is defined over a subset of k + d + 1 knots. Second, the configurations of k + d + 1 knots of S that are selected, are those for which there exists a sphere passing through d + 1 of the knots, the other k knots being inside the sphere, and the remaining knots of S being outside the sphere. These configurations are called Delaunay configurations. Applications using them can be found for example in [START_REF] Cao | Surface reconstruction using bivariate simplex splines on Delaunay configurations[END_REF][START_REF] Hansen | Adaptive parametrization of multivariate B-splines for image registration[END_REF].

In this paper, we propose a more general method to select configurations in the case d = 2, in that we replace circles by maximal families of convex pseudocircles. Recall that a family of convex pseudo-circles is a set of convex Jordan curves that pairwise intersect at most twice. We show that, if we take any family of configurations defined that way and which is maximal for inclusion, then the order-k simplex splines defined over these configurations span a bivariate spline space that satisfies the polynomial reproduction property. We also prove that such a family of configurations contains the same number of elements as the family of Delaunay configurations, i.e., the corresponding spline spaces are spanned by equal sized spanning sets.

In 2007, Liu and Snoeyink already pointed out that the generalization of Neamtu, while elegant, is restrictive in the types of splines that can be generated [START_REF] Liu | Quadratic and cubic B-splines by generalizing higherorder Voronoi diagrams[END_REF]. They proposed an algorithmic method to generate more general configurations in the case d = 2. They proved that their algorithm effectively constructs valid configurations up to k = 3. Even if experimental results indicate that the algorithm always works, this has never been proven in the general case (see in [START_REF] Oraiby | Centroid triangulations from k-sets[END_REF] a proof for some particular cases). Nevertheless, the simplex splines defined over the configurations constructed by their algorithm appear to be interesting in applications. In particular, they are efficient to represent surfaces with sharp features [START_REF] Liu | Bivariate B-splines from centroid triangulations[END_REF][START_REF] Zhang | Surface reconstruction using simplex splines on feature-sensitive configurations[END_REF], and as a basis for isogeometric analysis [START_REF] Cao | A finite element framework based on bivariate simplex splines on triangle configurations[END_REF].

In this paper we prove that the configurations constructed by the algorithm of Liu and Snoeyink are precisely the ones defined here with maximal families of convex pseudo-circles. This proves that the algorithm always works.

An extended abstract of the present paper can be found in [START_REF] Schmitt | Bivariate B-splines from convex pseudo-circle configurations[END_REF].

B-splines and configurations

Notations

For a subset E of the plane R 2 , conv(E) denotes its convex hull, ∂E its boundary, E its closure, and relint(E) its relative interior, i.e., its interior in the subspace of R 2 spanned by E. Unless otherwise stated, we consider S to be a finite set of n > 2 points in the plane, no three of them being collinear.

B-splines

Given a non-negative integer k and a sequence t 0 < t 1 < t 2 . . . < t k+1 of k + 2 reals, called knots, the order-k B-spline over t 0 , . . . , t k+1 can be defined for any x ∈ R using the following variant of the Cox-de Boor recurrence formula. When k = 0,

B(x|t 0 , t 1 ) = 1 t1-t0 if t 0 ≤ x < t 1 0 otherwise.
When k > 0, setting λ x = x-t0 t k+1 -t0 and 1 -λ x = t k+1 -x t k+1 -t0 the barycentric coordinates of x with respect to t 0 and t k+1 , B(x|t 0 , . . . , t k+1 ) = λ x B(x|t 0 , . . . , t k ) + (1 -λ x )B(x|t 1 , . . . , t k+1 ).

(1)

Simplex splines

As shown by Schoenberg [START_REF] Curry | On pólya frequency functions IV: The fundamental spline functions and their limits[END_REF], B-splines can be constructed by projecting higher dimensional simplices onto the real line. De Boor [START_REF] De Boor | Splines as linear combinations of B-splines. a survey[END_REF] extended this property to define multivariate B-splines, called simplex splines. Micchelli [START_REF] Micchelli | A constructive approach to kergin interpolation in R: multivariate b-splines and lagrange interpolation[END_REF] then showed that the recurrence formula defining B-splines can be extended to simplex splines. Let us recall this result in the case of bivariate simplex splines (see Figure 2).

In the bivariate case, knots are points in the plane R 2 . Let k be a nonnegative integer and let T be a set of k + 3 such knots, not all collinear. For any point x ∈ R 2 , let {λ t,x : t ∈ T } be a set of reals such that t∈T λ t,x t = x and t∈T λ t,x = 1, i.e., {λ t,x : t ∈ T } is any set of barycentric coordinates of x with respect to the knots t ∈ T . Denoting by area(conv(T )) the area of the convex hull of T , the order-k bivariate simplex spline over T satisfies the following relations at almost every point x ∈ R 2 : The points x ∈ R 2 where the relation is not satisfied are the points on the boundaries of the convex hulls conv(T ), where T is a subset of three points of S. The same issue would occur in the univariate case if B(x|t 0 , t 1 ) was set to 1 t1-t0 on the closed interval [t 0 , t 1 ]. We refer to [START_REF] Seidel | Polar forms and triangular B-spline surfaces, in: Blossoming: The New Polar-Form Approach to Spline Curves and Surfaces[END_REF] to see how the relation defining M (x|T ) in the case |T | = 3 can be modified in a similar way so that the recurrence relation holds true at every point x ∈ R 2 .

M (x|T ) =
When |T | > 3, Micchelli's result shows that the value of M (x|T ) does not depend on the choice of the barycentric coordinates λ t,x . Thus, we can select any subset Q of three non-collinear knots in T and set λ t,x to zero for all knots t in P = T \ Q. The non-zero λ t,x are then the unique barycentric coordinates of x with respect to Q satisfying q∈Q λ q,x q = x and q∈Q λ q,x = 1. Hence,

M (x|T ) = M (x|P ∪ Q) = q∈Q λ q,x M (x|P ∪ (Q \ {q})). (2)
From Section 3 on, we will furthermore impose that the points of Q are three extreme points of T , i.e., three vertices of conv(T ).

Configurations

Given a set S of more than k + 3 points in the plane, an order-k bivariate spline over S is a linear combination of simplex splines defined over subsets of k+3 points of S. Thus, we need a method to select subsets T of k+3 points of S, such that the simplex splines defined over these subsets span a bivariate spline space over S. From (2), this comes actually to select pairs (P, Q) of subsets of S such that P ∩ Q = ∅, |Q| = 3, and |P | = k. Such a pair (P, Q) is called a configuration of order k of S or, for short, a k-configuration of S. Furthermore, if the circle γ circumscribed to Q is such that γ ∩ S = Q and disk(γ) ∩ S = P , (P, Q) is also called a Delaunay k-configuration of S.

In [START_REF] Neamtu | Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay[END_REF], Neamtu proved that the spline space spanned by the family of Delaunay k-configurations satisfies the polynomial reproduction property, i.e., it contains all degree-k polynomials. He did so under some simplifying assumptions on the set S:

1. S is infinite: conv(S) = R 2 , 2.
S is locally finite: the intersection of S with any ball of R 2 is finite, and 3. S is in general position: no three points in S are collinear and no four points are cocircular.

He used the fact that every degree k polynomial f (x) can be written in polar form as F (x 1 , ..., x k ), where

-F is symmetric, i.e., if σ is a permutation of (x 1 , . . . , x k ), F (x 1 , . . . , x k ) = F (σ(x 1 , . . . , x k )), -F is multi-affine, i.e., ∀i ∈ {1, . . . , k}, F is linear in x i when x 1 , . . . , x i-1 ,
x i+1 , . . . , x k are fixed, and

-F (x 1 , . . . , x k ) = f (x) when x 1 = x 2 = . . . = x k = x.
For example, the polar form of f

(x) = ax 2 + bx + c is F (x 1 , x 2 ) = ax 1 x 2 + bx1 2 + bx2 2 + c. Theorem 1 states Neamtu's result. Theorem 1.
Let ∆ k be the family of Delaunay k-configurations of a set S of points in R 2 that is infinite, locally finite, and in general position. For every degree k polynomial f with polar form F ,

f (x) = (P,Q)∈∆ k F (P ) area(conv(Q)) M (x|P ∪ Q), x ∈ R 2 .
As pointed out by Liu and Snoeyink in [START_REF] Liu | Quadratic and cubic B-splines by generalizing higherorder Voronoi diagrams[END_REF], the proof of this theorem uses only two properties of Delaunay configurations. The first is that the family ∆ 0 of Delaunay 0-configurations induces a triangulation of S, in the sense that the triangles {conv(Q) : (∅, Q) ∈ ∆ 0 } form a triangulation of S. In fact, it is the well known Delaunay triangulation of S.

The second concerns edges of Delaunay configurations. Given any configuration (P, Q) of S, the edges of (P, Q) are all the pairs (P, Q \ {r}) and (P ∪ {r}, Q \ {r}), with r ∈ Q. The property of Delaunay configuration edges used in the proof of Theorem 1 is the following edge matching property.

Edge matching property. Every edge (R, {s, t}) of a Delaunay i-configuration, i ∈ {0, . . . , k}, is the common edge of precisely two Delaunay configurations. These configurations are of the form (R \ {r}, {r, s, t}) and (R \ {r }, {r , s, t}), with r, r two distinct points of S \ {s, t}. Each configuration is either of order |R| or of order |R| -1, depending on whether r, r belong to R or not. The two configurations are of distinct orders if and only if r and r are on the same side of (st).

It is not hard to understand why this property holds. Since no three points in S are cocircular, for any Delaunay configuration (P, Q) of S and for any r ∈ Q, there exists a circle passing through Q \ {r}, enclosing P , and such that all other points of S are outside the circle. There also exists a circle passing through Q \ {r} and that encloses precisely P ∪ {r}. It follows that, every edge of any Delaunay configuration of S is a pair (R, {s, t}) for which there exists a circle γ such that γ ∩ S = {s, t} and disk(γ) ∩ S = R. Now, γ can be continuously deformed, while remaining in the family of circles passing through s, t, until it meets a third point of S. During the deformation, the center of γ moves continuously on the bisector of s, t. If it moves towards the infinite direction of (st) -, the circle meets a point r that either is in (st) -and outside the initial circle γ, or is in (st) + and inside the initial circle γ (see Figure 3). In the first case, r belongs to (S \ (R ∪ {s, t})) ∩ (st) -, and (R \ {r}, {r, s, t}) = (R, {r, s, t}) is a Delaunay |R|-configuration of S. In the second case, r belongs to R ∩ (st) + , and (R \ {r}, {r, s, t}) is a Delaunay (|R| -1)-configuration of S. Such a point r always exists since S is infinite, and r is unique since S has no three cocircular points. Symmetrically, if the center of γ moves towards the infinite direction of (st) + , the circle meets exactly one point r of S \ {s, t}. Either r belongs to (S \(R∪{s, t}))∩(st) + , and (R\{r }, {r , s, t}) is a Delaunay |R|-configuration of S. Or r belongs to R ∩ (st) -, and (R \ {r }, {r , s, t}) is a Delaunay (|R| -1)-configuration of S. This proves the edge matching property.

γ γ 1 γ 2 s t r c 2 c 1 c r'
Figure 3: The pair (R, {s, t}) = (disk(γ) ∩ S, γ ∩ S) is the common edge of the two Delaunay configurations (R, {r, s, t}) = (disk(γ 1 ) ∩ S, γ 1 ∩ S) and (R \ {r }, {r , s, t}) = (disk(γ 2 ) ∩ S, γ 2 ∩ S). The points c, c 1 , and c 2 on the bisector of s, t are the respective centers of γ, γ 1 , and γ 2 .

Valid configurations in finite point sets

Since the next section will be based on enumeration results stated in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF] for finite point sets, we need to check how the above results apply when S is finite. First, the property that Delaunay 0-configurations induce the Delaunay triangulation of S obviously holds when S is finite. Secondly, the only Delaunay configuration edges for which we do not find a point r as in Section 2.4, are the edges of the form (R, {s, t}) with, at the same time, (S \ (R ∪ {s, t})) ∩ (st) -= ∅ and R ∩ (st) + = ∅, i.e., (st) -∩ S = R. Symmetrically, we do nor find a point r if and only if (st) + ∩ S = R. Therefore, the only Delaunay configuration edges where the edge matching property does not hold in finite point sets are those of the form (R, {s, t}) with (st) -∩ S = R (up to a permutation of s and t). Now, for such an edge, no point x of the half-plane (st) + belongs to conv(R ∪ {s, t}). From the definition of simplex splines, it follows that M (x|R ∪ {s, t}) = 0. This is the only argument that has to be added to Neamtu's proof, to show that Theorem 1 also holds when S is finite, provided that the domain of definition of f is restricted to the region {(st) + : s, t ∈ S, |(st) -∩ S| ≤ k}, usually called the depth-k region of S.

This leads to the following definition of the edge matching property for families of configurations in finite point sets.

Definition 1. Let ∆ be a family of (arbitrary) configurations of S. We say that ∆ satisfies the finite edge matching property if the (infinite) edge matching property holds for all edges of the configurations of ∆, except for the edges of the form (R, {s, t}) with (st) -∩ S = R (up to a permutation of s and t).

From the previous discussion, the only properties of the Delaunay configurations of S needed to prove Theorem 1 in the finite setting is that the family of Delaunay i-configurations, i ∈ {0, . . . , k}, verifies the finite edge matching property, and that the Delaunay 0-configurations induce a triangulation of S. Thus, Theorem 1 can be generalized to wider families of configurations, also in finite point sets.

Theorem 2. Let S be a finite set of n > 2 points in the plane, no three of them being collinear and let k ∈ {0, . . . , n -3}. Let {∆ 0 , . . . , ∆ k } be a set of families of configurations of S of order 0, . . . , k that satisfies the finite edge matching property and is such that ∆ 0 induces a triangulation of S. For every degree k polynomial f with polar form F and for every point x in the depth-k region of S, we have

f (x) = (P,Q)∈∆ k F (P ) area(conv(Q)) M (x|P ∪ Q).
Definition 2. We say that a family of k-configurations of S is valid (in the finite setting) when the spline space that it spans verifies the polynomial reproduction property over the subset of the plane restricted to the depth-k region of S.

From Theorem 2, a family ∆ k of k-configurations of S is valid if there exist families of configurations ∆ 0 , . . . , ∆ k-1 of order 0, . . . , k-1 such that ∆ 0 induces a triangulation of S and {∆ 0 , . . . , ∆ k } satisfies the finite edge matching property.

It is worth noting that such a family ∆ k enables to extend another fundamental property of univariate B-splines, namely the fact that the order-k normalized B-splines form a partition of unity. Recall that the univariate order-k normalized B-spline over a sequence t 0 < t 1 < . . . < t k+1 of reals is defined by N (x|t 0 , . . . , t k+1 ) = (t k+1 -t 0 )B(x|t 0 , . . . , t k+1 ). Given a sequence t 0 < t 1 < . . . < t n-1 of at least k + 2 reals, every real x in [t k , . . . , t n-k-1 ] satisfies

n-k-2 i=0
N (x|t i , . . . , t i+k+1 ) = 1. Now, define the bivariate order-k normalized simplex spline over a configuration (P, Q) of S to be N (x|P

∪ Q) = area(conv(Q))M (x|P ∪ Q).
Applying Theorem 2 with the constant polynomial f (x) = F (x) = 1 we get, for every point x in the depth-k region of S,

(P,Q)∈∆ k N (x|P ∪ Q) = 1.

Convex configurations

Convex pairs

Let us come back to the recurrence relations (1) and ( 2), which respectively define univariate B-splines and bivariate simplex splines. In (1), the knots t 0 , . . . , t k+1 are supposed to be consecutive in the whole sequence of knots, i.e., they form an interval that contains no other knot. Furthermore, t 0 and t k+1 are the endpoints of this interval. Thus, relation (2) becomes a natural generalization of (1) if we chose for T = P ∪ Q a subset of points of S whose convex hull contains no other point of S, and such that the points of Q are extreme points of T , i.e., vertices of the convex hull of T .

In the remainder of the paper, we will need the following more general definition that extends the notion of configuration. Definition 3. (i) An ordered pair (P, Q) is called a convex pair of S, if P and Q are disjoint subsets of S, conv(P ∪ Q) ∩ S equals P ∪ Q, and Q is a subset of the extreme points of P ∪ Q.

(ii) When |Q| = 3, the convex pair (P, Q) is also called a convex configuration of S, or a convex k-configuration of S, with k = |P |.

(iii) When Q = ∅, P is also called a convex subset of S; i.e., a subset P of S is a convex subset of S if conv(P ) ∩ S = P .

Since, for any convex pair (P, Q) of S, the convex hull of P ∪ Q contains no point of S \ (P ∪ Q) and since the points of Q are vertices of this convex hull, there exists a convex Jordan curve γ such that γ ∩ S = Q and disk(γ) ∩ S = P . We say that γ is a separating curve of (P, Q) in S. Conversely, every pair (P, Q) of subsets of S for which there exists such a convex Jordan curve, is a convex pair of S. Hence, Delaunay configurations are particular convex configurations: those whose separating curves are circles.

The following definition extends the notion of edges of convex configurations to convex pairs. Definition 4. Let (P, Q) be a convex pair of S.

(i) Every pair (P , Q ) such that P ∩ Q = ∅ and P ⊆ P ⊆ P ∪ Q ⊆ P ∪ Q is called a sub-pair of (P, Q).

(ii) When Q = ∅, P is also called a subset of (P, Q); i.e., a subset P of S is a subset of (P, Q) if P ⊆ P ⊆ P ∪ Q.

Clearly, the edges of a convex configuration (P, Q) of S are the sub-pairs (P , Q ) of (P, Q) with |Q | = 2.

Compatibility of convex pairs

The important result of Neamtu, recalled by Theorem 1, is that the family of Delaunay k-configurations is valid. Here we prove that this holds for any maximal family of convex k-configurations whose separating curves form a family of convex pseudo-circles. Recall that a family C of convex Jordan curves is said to form a family of convex pseudo-circles if any two curves in C either intersect properly at exactly two points, meet at exactly one point, or do not meet at all.

It is not hard to check that if two convex pairs admit separating curves that satisfy the pseudo-circle property, then these two pairs are compatible in the sense of the following definition (see also Figure 4). Definition 5. (i) Two distinct convex pairs (P, Q) and (P , Q ) of S are said to be compatible if relint(conv

((P ∪ Q) \ P )) ∩ relint(conv((P ∪ Q ) \ P )) = ∅.
(ii) A convex pair (P, Q) and a convex subset T of S are said to be compatible if (P, Q) and (T, ∅) are compatible.

(iii) Two convex subsets T and T are said to be compatible if (T, ∅) and (T , ∅) are compatible. More generally, one can show that a family of convex pairs admits a set of separating curves that form a set of convex pseudo-circles if and only if the convex pairs in the family are pairwise compatible. We do not prove this result here because the use of pseudo-circles is not necessary in this paper; all results will be stated in terms of compatibility of convex pairs. However, pseudo-circles give an intuitive idea of some definitions and results. Remark 1. Figure 4(b) shows why the use of relative interiors is needed in Definition 5(i) to characterize the compatibility of two convex pairs (P, Q) and (P , Q ). However, since no three points in S are collinear, if relint(conv((P ∪Q)\ P ))∩relint(conv((P ∪Q )\P )) = ∅, then conv((P ∪Q)\P ) and conv((P ∪Q )\ P ) can only intersect in points of (P ∪ Q) \ P ∩ (P ∪ Q ) \ P = Q ∩ Q . It follows that the relative interiors can be removed in the definition of compatibility when Q ∩ Q = ∅. This notably implies that two convex subsets T and T are compatible if and only if conv

(T \ T ) ∩ conv(T \ T ) = ∅.
The results of Proposition 1 below, which were proved in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF], serve to characterize families of compatible configurations.

Proposition 1. (i) If (P, Q) is a convex pair of S with |Q| ≤ 3, then every sub-pair (P , Q ) of (P, Q) distinct from (P, Q) is a convex pair of S compatible with (P, Q).
(ii) Two distinct convex pairs (P, Q) and (P , Q ) are compatible if and only if the subsets of (P, Q) are compatible with the subsets of (P , Q ).

An immediate consequence of this proposition is that: Proposition 2. If (P, Q) and (P , Q ) are two compatible convex pairs of S with |Q| ≤ 3 and |Q | ≤ 3, then every sub-pair of (P , Q ) distinct from (P, Q) is a convex pair of S compatible with (P, Q).

Proof. From Proposition 1(ii), the subsets of (P , Q ) are convex pairs of S compatible with the subsets of (P, Q). Now, by Definition 4, any subset of a sub-pair of (P , Q ) is also a subset of (P , Q ). It follows from Proposition 1(ii), that the sub-pairs of (P , Q ) are also compatible with (P, Q).

In the sequel of the paper, we will say that a family of compatible convex pairs is maximal if it is maximal for inclusion. We will also say that two families of compatible convex pairs are compatible (with one another) if the elements of the two families are pairwise compatible.

As already mentioned, we will need different results that have been proved in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF]. However, these results applied to maximal families of convex subsets. Before we can apply them to families of convex configurations, we need to connect these two kinds of families. Using Proposition 1, the following proposition provides this connection. Proposition 3. (i) If two convex configurations of S are compatible with a maximal family of compatible convex subsets of S, then the two configurations are compatible with one another.

(ii) If ∆ is a family of compatible convex configurations of S, then there exists a maximal family of compatible convex subsets of S that is compatible with ∆.

(iii) If ∆ k is a maximal family of compatible convex k-configurations of S and if F is a maximal family of compatible convex subsets of S that is compatible with ∆ k , then ∆ k is the set of all convex k-configurations of S that are compatible with F.

Proof. (i) If a convex configuration of S is compatible with a family F of compatible convex subsets of S then, from Proposition 1(ii), its subsets are compatible with F. Therefore, they belong to F if F is maximal. Thus, from Proposition 1(ii), two convex configurations of S compatible with F are compatible with one another.

(ii) From Proposition 1(ii), the subsets of the configurations in ∆ are pairwise compatible. Thus, they belong to a same family of compatible convex subsets of S, which can always be made maximal.

(iii) From (i), every convex k-configuration of S compatible with F is compatible with ∆ k . Thus, it belongs to ∆ k if ∆ k is maximal.

Validity of compatible convex configurations

Proposition 4 below, which comes from [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF], provides the missing tool to extend the finite edge matching property to compatible convex configurations.

Proposition 4. Given a family F of compatible convex subsets of S, for every convex pair (P, {s, t}) of S compatible with F such that (st) -∩ S = P , there exists a point r ∈ (P ∩ (st) + ) ∪ ((S \ P ) ∩ (st) -) such that (P \ {r}, {r, s, t}) is a convex pair of S compatible with F.

The direct proof of this proposition, as suggested in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF] and detailed in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF], is cumbersome. An indirect but shorter proof can be given with the help of the centroid triangulations used in Section 4.

Proposition 5. Let ∆ k be a maximal family of compatible convex k-configurations of S. Let F be a maximal family of compatible convex subsets of S compatible with ∆ k . For any i ∈ {0, . . . , k -1}, let ∆ i be the family of convex i-configurations of S compatible with F.

(i) The set {∆ 0 , . . . , ∆ k } satisfies the finite edge matching property.

(ii) The family ∆ 0 induces a triangulation of S.

Proof. (i.1) Let (P, {s, t}) be an edge of a configuration of {∆ 0 , . . . , ∆ k } such that neither (st) -∩ S nor (st) + ∩ S = (ts) -∩ S is equal to P . By the definition of edges of configurations, (P, {s, t}) is a sub-pair of a configuration of {∆ 0 , . . . , ∆ k } and, by Proposition 2, (P, {s, t}) is a convex pair of S compatible with F. Thus, from Proposition 4, there exist r ∈ (P ∩ (st) + ) ∪ ((S \ P ) ∩ (st) -) and r ∈ (P ∩ (st) -) ∪ ((S \ P ) ∩ (st) + ) such that (P \ {r}, {r, s, t}) and (P \ {r }, {r , s, t}) are convex configurations of S compatible with F, i.e., configurations of {∆ 0 , . . . , ∆ k }. Now, by definition of edges, (P, {s, t}) is an edge of both configurations and, by construction, r and r are distinct. Therefore (P, {s, t}) is an edge of two distinct configurations of {∆ 0 , . . . , ∆ k }. Furthermore, r and r are on the same side of (st Suppose, by contradiction, that there exists q = r that belongs to (P ∩ (st) + ) ∪ ((S \ P ) ∩ (st) -) and such that (P \ {q}, {q, s, t}) is also a configuration of {∆ 0 , . . . , ∆ k }. From Proposition 3(i), (P \ {q}, {q, s, t}) is compatible with (P \ {r}, {r, s, t}). Setting R = ((P \ {q}) ∪ {q, s, t}) \ (P \ {r}) = (P ∪ {q, s, t}) \ (P \ {r}) and R = ((P \ {r}) ∪ {r, s, t}) \ (P \ {q}) = (P ∪ {r, s, t}) \ (P \ {q}), it follows from Definition 5 that relint(conv(R)) ∩ relint(conv(R )) = ∅.

)
In the case where exactly one of q, r is in P , q and r are on both sides of (st), by construction of q, r. Furthermore, within a permutation of R and R , we have R = {s, t} and R = {q, r, s, t}, in contradiction with relint(conv(R)) ∩ relint(conv(R )) = ∅.

In the other cases, q and r are on the same side of (st). Furthermore, within a permutation of R and R , we have R = {r, s, t} and R = {q, s, t}, again in contradiction with relint(conv(R)) ∩ relint(conv(R )) = ∅.

It results that there exists a unique point r ∈ (P ∩ (st) + ) ∪ ((S \ P ) ∩ (st) -) such that (P \ {r}, {r, s, t}) ∈ {∆ 0 , . . . , ∆ k }.

In the same way, there exists a unique point r ∈ (P ∩(st) -)∪((S \P )∩(st) + ) such that (P \ {r }, {r , s, t}) ∈ {∆ 0 , . . . , ∆ k }.

(i.

3) It follows from (i.1) and (i.2) that {∆ 0 , . . . , ∆ k } satisfies the finite edge matching property.

(ii) Let T 0 be the set of triangles rst such that (∅, {r, s, t}) ∈ ∆ 0 . From Definition 3, conv({r, s, t}) ∩ S = {r, s, t}. From Proposition 3(i), since ∆ 0 is compatible with F, the configurations in ∆ 0 are compatible with each others and, therefore, from Definition 5, the triangles of T 0 have disjoint interiors.

Consider now an edge of a triangle of T 0 , say the edge [s, t] of rst, oriented such that r ∈ (st) + . By Definition 4, (∅, {s, t}) is a sub-pair of (∅, {r, s, t}) and, by Proposition 2, (∅, {s, t}) is compatible with F. If [s, t] is not an edge of conv(S), then (st) -∩ S = ∅ and, from Proposition 4, there exists r ∈ S ∩ (st) -such that (∅, {r , s, t}) is a convex 0-configuration of S compatible with F. Hence, [s, t] is a common edge of two triangles of T 0 , which are on both sides of [s, t]. By induction, the set of triangles of T 0 covers conv(S) and, therefore, triangulates S.

The following theorem is an immediate consequence of Proposition 5 and Theorem 2.

Theorem 3. Given a set S of n > 2 points in the plane, no three of them collinear, and an integer k ∈ {0, . . . , n -2}, every maximal family of compatible convex k-configurations of S is valid.

The number of compatible convex k-configurations

A valid family of configurations can only be useful in practice if it has not too many elements, i.e., the basis of the spanned spline space must not be too large. In this section we compare the size of any family of compatible convex configurations with the size of the family of Delaunay configurations.

Counting Delaunay k-configurations

The number of Delaunay k-configurations can be counted using the order-(k + 1) Voronoi diagram. Recall first that the order-k Voronoi diagram of a planar point set S partitions the plane into regions such that the points of the plane in a same region have the same k nearest neighbors in S (see Figure 5). When the set S contains no four cocircular points, every vertex of the order-k Voronoi diagram is the intersection point of precisely three regions. It is not hard to check that such a point is the center of a circle passing through three points of S and enclosing precisely either k -1 or k -2 points of S. Conversely, every point of the plane that is the center of such a circle is a vertex of the order-k Voronoi diagram of S. The vertices that are centers of circles enclosing precisely k -1 points were called new vertices in [START_REF] Lee | On k-nearest neighbor Voronoi diagrams in the plane[END_REF]. In order to enumerate these vertices, we need to recall the definition of k-sets.

2(k + 1)(n -1) -k(k + 1) - k+1 i=1 a i (S).
Notice that this number is linear with the number n of points of S when the order k is considered as a constant.

Centroid triangulations

The order-k Voronoi diagram of S admits a dual triangulation, called the order-k centroid Delaunay triangulation of S, whose vertices are the centroids of the k-point subsets of S that define the order-k Voronoi regions (see [START_REF] Schmitt | On Delaunay and Voronoi diagrams of order k in the plane[END_REF][START_REF] Aurenhammer | A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams[END_REF] and Figure 5). Similar triangulations can be defined using maximal families of compatible convex k-configurations. To this aim, we first extend the definition of convex hulls to the order k, by using the notion of k-set polygon introduced by Edelsbrunner, Valtr, and Welzl [START_REF] Edelsbrunner | Cutting dense point sets in half[END_REF].

Definition 7. The k-set polygon of S, denoted by Q k (S), is the convex hull of the centroids of all k-point subsets of S.

Clearly, Q 1 (S) is the convex hull of S. Thus, the vertices of Q 1 (S) are the points of S that can be separated from the others by a straight line. The vertices of Q k (S), for any k, have been characterized in a similar way by Andrzejak and Fukuda [START_REF] Andrzejak | Optimization over k-set polytopes and efficient k-set enumeration[END_REF]. The characterization of the edges of Q k (S) is due to Andrzejak and Welzl [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)partitions[END_REF].

Recall that we assume that no three points in S are collinear, and denote by g(T ) the centroid of any subset T of S. (ii) If s and t are two distinct points of S such that the set P = (st) -∩ S has cardinality k -1, then [g(P ∪ {s}), g(P ∪ {t})] is an edge of Q k (S) oriented in counterclockwise direction on ∂Q k (S). Every edge of Q k (S) is determined that way by a unique pair (P, {s, t}).

Notice that, from Section 2.5, the pairs (P, {s, t}) such that P = (st) -∩ S are precisely the configuration edges where the edge matching property is not satisfied in finite point sets. The next proposition shows that these pairs belong to the set of edges of every maximal family of compatible convex configurations. It also shows a similar result for k-sets. Proposition 7. (i) Every k-set of S is a convex subset of S and is compatible with every convex pair of S.

(ii) Every pair (P, {s, t}) of S such that (st) -∩ S = P is a convex pair of S and is compatible with every other convex pair of S.

Proof. (i) If T is k-set of S, T is separable from S \ T by a straight-line l. Therefore, conv(T ) ∩ S equals T , implying that T is a convex subset of S.
For any other convex subset T of S, T \ T and T \ T are on both sides of l, implying that T is compatible with T . Thus, T is compatible with the subsets of every convex pair of S and therefore, from Proposition 1(ii), T is compatible with the pair itself.

(ii) Since no three points in S are collinear, we have (st) ∩ S = {s, t}. Thus, (st) -∩ S = P implies that conv(P ∪ {s, t}) ∩ S equals P ∪ {s, t}, and that s, t are extreme points of P ∪ {s, t}. Therefore, (P, {s, t}) is a convex pair of S. Now, the subsets of (P, {s, t}) are the sets P , P ∪ {s}, P ∪ {t}, and P ∪ {s, t}. All these sets are i-sets of S, with i ∈ {|P |, |P | + 1, |P | + 2}. Therefore, from (i), they are convex subsets of S and are compatible with any convex pair of S. From Proposition 1(ii), it follows that (P, {s, t}) is compatible with any convex pair of S.

In order to triangulate the k-set polygon of S, we associate centroid triangles with the convex configurations of S. Such centroid triangles have already been introduced in the literature, associated with different kinds of configurations, both in the plane [START_REF] Schmitt | On Delaunay and Voronoi diagrams of order k in the plane[END_REF][START_REF] Aurenhammer | A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams[END_REF][START_REF] Liu | Quadratic and cubic B-splines by generalizing higherorder Voronoi diagrams[END_REF] and in space [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)partitions[END_REF][START_REF] Schmitt | k-set polytopes and order-k Delaunay diagrams[END_REF][START_REF] Edelsbrunner | Poisson-Delaunay mosaics of order k[END_REF]. Definition 8. (i) For every convex configuration (P, {r, s, t}) of S, the triangle whose vertices are the centroids g(P ∪ {r}), g(P ∪ {s}), g(P ∪ {t}) is called the type-1 centroid triangle associated with (P, {r, s, t}). The triangle whose vertices are the centroids g(P ∪ {r, s}), g(P ∪ {s, t}), g(P ∪ {r, t}) is called the type-2 centroid triangle associated with (P, {r, s, t}).

(ii) For every convex pair (P, {s, t}) of S, the line segment [g(P ∪ {s}), g(P ∪ {t})] is called the centroid segment associated with (P, {s, t}). Proposition 8. Let (P, {r, s, t}) be a convex configuration of S, and let τ 1 and τ 2 be the type-1 and the type-2 centroid triangles associated with (P, {r, s, t}).

(i) The vertices of τ 1 are the centroids of the three subsets of (P, {r, s, t}) of size |P | + 1. The edges of τ 1 are the centroid segments associated with the three edges (R, {u, v}) of (P, {r, s, t}) such that R = P .

(ii) The vertices of τ 2 are the centroids of the three subsets of (P, {r, s, t}) of size |P | + 2. The edges of τ 2 are the centroid segments associated with the three edges (R, {u, v}) of (P, {r, s, t}) such that R = P ∪{w}, with {u, v, w} = {r, s, t}.

Proof. (i) The first statement is an immediate consequence of Definition 4(ii). The edges of τ 1 are the three segments of the form [g(P ∪ {u}), g(P ∪ {v})], with {u, v} ⊂ {r, s, t}. By Definition 4(i), the pair (P, {u, v}) is a sub-pair of (P, {r, s, t}); more precisely, (P, {u, v}) is an edge of (P, {r, s, t}). By Proposition 1, (P, {u, v}) is a convex pair of S. Therefore, by Definition 8(ii), [g(P ∪ {u}), g(P ∪ {v})] is the centroid segment associated with (P, {u, v}).

(ii) The first statement is also an immediate consequence of Definition 4(ii). The edges of τ 2 are the three segments of the form [g(P ∪ {w, u}), g(P ∪ {w, v})], with {u, v, w} = {r, s, t}. Again, the pair (P ∪ {w}, {u, v}) is an edge of the configuration (P, {r, s, t}) and is a convex pair of S. By Definition 8(ii), [g(P ∪ {w, u}), g(P ∪ {w, v})] is the centroid segment associated with (P ∪ {w}, {u, v}).

The following theorem recalls a result of [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF] that characterizes sets of centroid triangles that triangulate the k-set polygon of S.

Theorem 5. Let F be a maximal family of compatible convex subsets of S and, for every i ∈ {0, . . . , n -3}, let ∆ i be the family of convex i-configurations of S that are compatible with F. Set ∆ -1 = ∆ n-2 = ∅ and let k ∈ {0, . . . , n -2}.

(i) The type-1 centroid triangles associated with the configurations in ∆ k and the type-2 centroid triangles associated with the configurations in ∆ k-1 have pairwise disjoint interiors and form a triangulation T k+1 of the (k + 1)-set polygon of S (see Figure 6). Remark 2. (i) It is crucial to notice here that every vertex of the triangulation T k+1 is uniquely determined by ∆ k-1 ∪ ∆ k in the following sense. Every vertex x of T k+1 is a vertex of at least one centroid triangle of T k+1 , and this triangle is associated with a convex configuration (P,

Q) of ∆ k-1 ∪∆ k . From Proposition 8,
x is the centroid of a (k + 1)-subset T of (P, Q). If x is a vertex of a second triangle of T k+1 associated with a second convex configuration (P , Q ) of ∆ k-1 ∪ ∆ k , let T be the (k + 1)-subset of (P , Q ) such that x = g(T ). Since ∆ k-1 and ∆ k are compatible with F, it follows from Proposition 2, that T and T are compatible with F. Since F is maximal, they belong to F. Thus, from Theorem 5(ii), T equals T .

If x is a vertex of Q k+1 (S), from Proposition 6(i), T is a (k + 1)-set of S.

(ii) In the same sense, the edges of T k+1 are uniquely determined by ∆ k-1 ∪ ∆ k . Every edge e of T k+1 is an edge of at least one triangle of T k+1 , which is associated with a convex configuration (P, Q) of ∆ k-1 ∪∆ k . From Proposition 8, e is the centroid segment associated with an edge (R, {u, v}) of (P, Q).

If e is an edge of a second triangle associated with a convex configuration (P , Q ) of ∆ k-1 ∪ ∆ k , e is also the centroid segment associated with an edge (R , {u , v }) of (P , Q ). Now, from Proposition 2, (R, {u, v}) and (R , {u , v }) are compatible with F. Therefore, from Theorem 5(iii) (R, {u, v}) equals (R , {u , v }).

If the edge e is an edge of Q k+1 (S), from Proposition 6(ii), up to a permutation of u and v, we have R = (uv) -∩ S.

The triangulation T k+1 defined by Theorem 5 is called the order-(k + 1) centroid triangulation of S associated with F. Notice that T 1 is the triangulation of S induced by ∆ 0 .

Let us finally state a structural property of the centroid triangulation T k+1 that will serve in the next section for the iterative construction of centroid triangulations.

Definition 9. Given a (k + 2)-subset T of S, consider the set composed of the type-2 centroid triangles of T k+1 and of the centroid segments of T k+1 that are all associated with convex pairs of S of the form (P, Q) with P ∪ Q = T . If this set is nonempty, it is called the domain of T in T k+1 . Remark 3. From Proposition 8(ii), the edges of a type-2 centroid triangle of T k+1 belong to the same domain as the triangle. This implies that two type-2 centroid triangles of T k+1 that share a common edge belong to the same domain. Domains satisfy the following stronger property proved in [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF] (see also Figure 6). Proposition 9. Every domain in T k+1 is either reduced to a line segment or forms a triangulation of the vertices of a convex polygon.

Counting compatible convex configurations

In order to count the number of triangles in a centroid triangulation, we first recall the following result of [START_REF] Chevallier | Separation by convex pseudo-circles[END_REF] on its number of vertices. Theorem 6. Given a maximal family F of compatible convex subsets of S and an integer k ∈ {0, . . . , n-2}, the number of vertices of the order-(k +1) centroid triangulation of S associated with F equals

2kn + n -k(k + 2) - k i=1 a i (S),
with the convention b a = 0 when b < a. Now, counting the number of type-1 triangles of a centroid triangulation leads to the following result. Theorem 7. For any k ∈ {0, . . . , n-3}, the number of elements of any maximal family ∆ k of compatible convex k-configurations of S equals

2(k + 1)(n -1) -k(k + 1) - k+1 i=1 a i (S).
Proof. (i) First, consider a maximal family F of compatible convex subsets of S. From Theorem 5(i), the number of convex k-configurations of S compatible with F equals the number of type-1 centroid triangles of the order-(k + 1) centroid triangulation T k+1 of S associated with F. From Theorem 6, T k+1 has

s k+1 = 2kn + n -k(k + 2) - k i=1 a i (S)
vertices. Now, T k+1 is a triangulation of the (k + 1)-set polygon Q k+1 (S) of S. From Proposition 6(i), the number of vertices of Q k+1 (S) is equal to the number a k+1 (S) of (k + 1)-sets of S. Hence, from the classical relations expressing the number of triangles in a triangulation in terms of its number of vertices, the total number of triangles of T k+1 equals

t k+1 = 2s k+1 -a k+1 (S) -2 = 4kn + 2n -2k(k + 2) -2 -2 k i=1 a i (S) -a k+1 (S). Now, the number t (1)
k+1 of type 1 triangles of T k+1 is equal to t k+1 minus the number of type-2 triangles of T k+1 . From Theorem 5(i), if k ≥ 1, the number of type-2 triangles of T k+1 equals the number of type-1 triangles of T k . Furthermore, T 1 is a triangulation of S and has no type-2 triangle. Hence the induction relation:

t (1) k+1 = 4kn + 2n -2k(k + 2) -2 -2 k i=1 a i (S) -a k+1 (S) -t (1) k , k ≥ 1 t (1) 1 = t 1 = 2n -a 1 (S) -2.
Solving this relation, we obtain

t (1) k+1 = 2(k + 1)(n -1) -k(k + 1) - k+1 i=1 a i (S).
(ii) From Proposition 3(ii), there exists a maximal family F of compatible convex subsets of S that is compatible with ∆ k . Furthermore, from Proposition 3(iii), since ∆ k is maximal, ∆ k is the set of all k-configurations of S that are compatible with F. Thus, from (i), ∆ k admits 2(k + 1)(n -1) -k(k + 1) -k+1 i=1 a i (S) elements. This somewhat surprising result shows that any maximal family of compatible convex k-configurations of a given points set S (no three of them collinear) has the same number of elements. Furthermore, from Theorem 4, this number equals the number of Delaunay k-configurations of S, if no four points in S are cocircular. Thus, from the point of view of the size of their bases, spline spaces generated by compatible convex configurations are as practical to use as the spline space generated by the Delaunay configurations.

The following corollary, which is the reciprocal of Proposition 3(iii), is a consequence of the proof of Theorem 7.

Corollary 1. Given a maximal family F of compatible convex subsets of S, the convex k-configurations of S that are compatible with F form a maximal family of compatible convex k-configurations of S.

Proof. From Proposition 3(i), the convex k-configurations of S compatible with F are pairwise compatible. From proof (i) of Theorem 7, their number equals 2(k + 1)(n -1) -k(k + 1) -k+1 i=1 a i (S). Now, from Theorem 7, this is also the number of elements of any maximal family of compatible convex k-configurations of S. It follows that the family of k-configurations of S compatible with F is maximal.

Generation of valid configurations

In this section, we address the problem of constructing maximal families of convex configurations.

Links in convex configurations

In [START_REF] Liu | Quadratic and cubic B-splines by generalizing higherorder Voronoi diagrams[END_REF], Liu and Snoeyink already proposed an algorithm to construct valid configurations. Their method is based on the following notion of link. Definition 10. Let ∆ k be a family of (arbitrary) k-configurations of S, and let T be a (k + 1)-subset of S for which there exists a configuration (P, {r, s, t}) in ∆ k with P ∪ {r} = T .

(i) The subset T is called a vertex of the configuration (P, {r, s, t}), and is also called a vertex of the family ∆ k .

(ii) The segment [s, t] oriented such that r ∈ (st) + is called the link of T in the configuration (P, {r, s, t}).

(iii) The set of links of T in all configurations of ∆ k from which T is a vertex is called the link of T in ∆ k .

In order to illustrate this definition by examples, consider a family ∆ 0 of 0-configurations of S that induces a triangulation T of S. Since P is empty in every 0-configuration (P, {r, s, t}), it follows from Definition 10 that the vertices of ∆ 0 are the vertices of the triangles of T , i.e., the vertices of T . For every such vertex r, the link of r in ∆ 0 is the polyline that links together, in counterclockwise order, the neighbors of r in T . The polyline is open when r is a vertex of ∂conv(S), and is closed otherwise. In Figure 7(a), the link of 7 is the oriented closed polyline [START_REF] Neamtu | What is the natural generalization of univariate splines to higher dimensions?[END_REF][START_REF] Cao | Surface reconstruction using bivariate simplex splines on Delaunay configurations[END_REF][START_REF] Neamtu | Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay[END_REF][START_REF] Dahmen | Recent progress in multivariate splines[END_REF][START_REF] De Boor | Topics in multivariate approximation theory[END_REF] and the link of 1 is the oriented open polyline [START_REF] De Boor | Splines as linear combinations of B-splines. a survey[END_REF][START_REF] Cao | Surface reconstruction using bivariate simplex splines on Delaunay configurations[END_REF][START_REF] Hansen | Adaptive parametrization of multivariate B-splines for image registration[END_REF][START_REF] De Boor | Topics in multivariate approximation theory[END_REF]. Figure 7(b) gives an example of two links in a family of 1-configurations of the same point set.

Centroid triangulations provide a nice way to represent links in maximal families of convex k-configurations. Indeed, by Definition 10, a (k + 1)-point subset T of S is a vertex of a convex k-configuration (P, {r, s, t}) of S if, up to a permutation of r, s, t, we have T = P ∪ {r}. Thus, T is a subset of (P, {r, s, t}) and is convex by Proposition 1. By Definition 8, g(T ) is a vertex of the type-1 centroid triangle associated with (P, {r, s, t}). Furthermore, the link [s, t] of T in (P, {r, s, t}) is the image of the edge [g(P ∪ {s}), g(P ∪ {t})] of this triangle by the homothety of center g(P ) and ratio k + 1. Now, from Proposition 3(ii) and (iii), for every maximal family ∆ k of compatible convex k-configurations of S, there exists a maximal family F of compatible convex subsets of S such that ∆ k is the set of all convex k-configurations of S compatible with F. Let T k+1 be the order-(k + 1) centroid triangulation of S associated with F. Determining the link of a vertex T of ∆ k comes down to considering the set of type-1 centroid triangles that have g(T ) as a vertex in the triangulation T k+1 , and to taking a homothetic image of the edge opposite to g(T ) in each triangle (see Figure 8). The algorithm of Liu and Snoeyink (see Algorithm 1) uses links to generate a family of (k + 1)-configurations, starting from a family of k-configurations.

Algorithm 1: To apply to a family ∆ k of k-configurations initialize ∆ k+1 to an empty set for every vertex T of ∆ k do let L be the link of T in ∆ k if L is not reduced to a segment (or to overlapping segments) then compute a constrained triangulation of L for every triangle rst of this triangulation do add the configuration (T, {r, s, t}) to ∆ k+1 return ∆ k+1

The algorithm is described in the case of infinite and locally finite point sets. According to its authors, the algorithm is well-defined when every link L, not reduced to a line segment, forms a simple polygon. Furthermore, they proved that, if ∆ k is a family of k-configurations whose links satisfy this property and if ∆ k is valid, i.e., if the order-k simplex splines defined over ∆ k reproduce g({1,7}) g({4,7}) The order-1 centroid triangulation T 1 (thin dashed lines) and the order-2 centroid triangulation T 2 (thin full lines) induced by the families ∆ 0 and ∆ 1 of compatible convex 0and 1-configurations of the caption of Figure 7. The four sick dashed segments are the edges opposite to the vertex g({4, 7}) in the type-1 centroid triangles (white) around g({4, 7}) in T 2 . These edges are homothetic images of the edges of the link of {4, 7} in ∆ 1 (see Figure 7(b)). The three sick full segments are the homothetic images of the edges of the link of {1, 7} in ∆ 1 .

all degree-k polynomials, then the generated set ∆ k+1 is also a valid family of (k + 1)-configurations. However, it is unclear whether or not the links in ∆ k+1 are again line segments or simple polygons. Therefore, it is not known whether the algorithm can be applied iteratively to generate valid families of configurations of higher orders. We prove here that it is the case if the algorithm is applied to our maximal families of convex configurations. To this aim, we first need to characterize links in families of convex configurations of finite point sets. Proof. (a) From Proposition 3(ii) and (iii), ∆ k is the set of convex k-configurations of S compatible with a maximal family F of compatible convex subsets of S. Let ∆ k-1 = ∅ when k = 0. Otherwise, let ∆ k-1 be the set of convex (k -1)-configurations of S compatible with F. From Theorem 5, the type-1 centroid triangles associated with the configurations in ∆ k and the type-2 centroid triangles associated with the configurations in ∆ k-1 form the order-(k + 1) centroid triangulation T k+1 of S associated with F. Recall that the boundary of T k+1 is the boundary of the (k + 1)-set polygon Q k+1 (S) of S.

Let T be a vertex of ∆ k . By Definitions 10 and 8, g(T ) is the vertex of at least one type-1 triangle in T k+1 . Let τ 0 , τ 1 , . . . , τ m be all the type-1 triangles with vertex g(T ) in T k+1 ordered in counterclockwise direction around g(T ), and such that (see also Figure 9):

-if g(T ) is not a vertex of Q k+1 (S), then τ m = τ 0 , -if g(T ) is a vertex of Q k+1 (S), then the complementary of Q k+1 (S) is
between τ m and τ 0 in counterclockwise direction around g(T ).

For every i ∈ {0, . . . , m}, let (P i , {r i , s i , t i }) be the convex configuration of ∆ k from which τ i is the associated triangle. The points r i , s i , t i are given such that (g(P i ∪ {r i }), g(P i ∪ {s i }), g(P i ∪ {t i })) is the counterclockwise ordered sequence of vertices of τ i , and such that P i ∪ {r i } = T (this is always possible since, by Remark 2(i), the vertices of T k+1 are uniquely determined). By construction, the link

L of T in ∆ k is composed of the oriented segments [s 0 , t 0 ], [s 1 , t 1 ], . . . [s m , t m ], with [s m , t m ] = [s 0 , t 0 ] when g(T ) is not a vertex of Q k+1 (S).
g(P 0 [{s 0 }) (b) Let us first show that L is an oriented polyline. More precisely, for every i ∈ {0, . . . , m -1}, t i = s i+1 .

g(P 0 [{t 0 }) = g(P 1 [{s 1 }) g(P 1 [{t 1 }) g(P 2 [{s 2 }) g(P 2 [{t 2 }) g(P i [{r i }) = g(T ) τ 0 τ 1 τ 2
From Remark 2(ii), if the edge [g(P i ∪ {r i }), g(P i ∪ {t i })] of τ i coincides with the edge [g(P i+1 ∪ {r i+1 }), g(P i+1 ∪ {s i+1 })] of τ i+1 then (P i , {r i , t i }) and (P i+1 , {r i+1 , s i+1 }) are equal convex pairs of S. Furthermore, since P i ∪ {r i } = P i+1 ∪ {r i+1 } = T , we have t i = s i+1 .

If [g(P i ∪ {r i }), g(P i ∪ {t i })] and [g(P i+1 ∪ {r i+1 }), g(P i+1 ∪ {s i+1 })] do not coincide, all triangles of T k+1 between τ i and τ i+1 in counterclockwise direction around g(T ) are of type 2. From Remark 3, they belong to a same domain and the edges [g(P i ∪ {r i }), g(P i ∪ {t i })] and [g(P i+1 ∪ {r i+1 }), g(P i+1 ∪ {s i+1 })] also belong to this domain. Thus, by Definition 9, we have P i ∪ {r i , t i } = P i+1 ∪ {r i+1 , s i+1 }, implying t i = s i+1 , since P i ∪ {r i }) = P i+1 ∪ {r i+1 }.

(c) We show now that two open segments of L either coincide or are disjoint, and that three distinct segments of L cannot share a common endpoint.

Let τ i and τ j be two distinct type-1 triangles with vertex g(T ). Since (P i , {r i , s i , t i }) and (P j , {r j , s j , t j }) are compatible by Proposition 3(i), it follows from Definition 5 that the relative interiors of conv(P i ∪ {r i , s i , t i } \ P j ) and of conv(P j ∪ {r j , s j , t j } \ P i ) are disjoint. Since P i ∪ {r i } = P j ∪ {r j }, this means that the interiors of the triangles r j s i t i and r i s j t j are disjoint. Since no three points of S are collinear, it follows that the open links ]s i , t i [ and ]s j , t j [ either are disjoint or coincide.

Let now τ i , τ j , and τ l be three distinct type-1 triangles with vertex g(T ). Suppose that the three links [s i , t i ], [s j , t j ], and [s l , t l ] share a common endpoint, i.e., there exist u i ∈ {s i , t i }, u j ∈ {s j , t j }, and u l ∈ {s l , t l } such that u i = u j = u l . Since P i ∪ {r i } = P j ∪ {r j } = P l ∪ {r l } = T , the edges [g(T ), g(P i ∪ {u i })], [g(T ), g(P j ∪ {u j })], and [g(T ), g(P l ∪ {u l })] of τ i , τ j , and τ l belong all to the same domain, the domain of T ∪ {u i } = T ∪ {u j } = T ∪ {u l }. At least two of these edges, say [g(T ), g(P i ∪{u i })] and [g(T ), g(P j ∪{u j })] do not coincide since τ i , τ j , and τ l have disjoint interiors. From Proposition 9, the domain to which these edges belong is a convex polygon. Thus, if we turn from [g(T ), g(P i ∪{u i })] to [g(T ), g(P j ∪ {u j })] around g(T ), in one of the two directions we only traverse edges and triangles of this domain. Since the type-1 triangles τ i and τ j adjacent to [g(T ), g(P i ∪ {u i })] and [g(T ), g(P j ∪ {u j })] do not belong to the domain, the edge [g(T ), g(P l ∪{u l })] must be one of the traversed edges. Therefore, the type-1 triangle τ l from which it is an edge must be one of the traversed triangles. This being impossible, [s i , t i ], [s j , t j ], and [s l , t l ] cannot have a common endpoint.

(d) We now complete the proof of (i), i.e., the case where T is not a (k+1)-set of S. From Proposition 6, g(T ) is an inner vertex of T k+1 and is therefore the vertex of at least three triangles. At least two of them must be type-1 triangles, otherwise, from Remark 3, all other triangles would belong to the same domain, which is impossible since the domains are convex.

From (a), if g(T ) is the vertex of precisely two type-1 triangles τ 0 = τ 2 and τ 1 then the link L of T is composed of the two segments [s 0 , t 0 ] = [s 2 , t 2 ] and [s 1 , t 1 ]. From (b), we have t 0 = s 1 and t 1 = s 2 = s 0 . Thus, L is reduced to overlapping segments with opposite orientations.

If g(T ) is the vertex of at least three type-1 triangles then, from (b) and (c), L forms a simple closed oriented polyline with at least three vertices.

(e) We finally complete the proof of (ii), the case where T is a (k + 1)-set of S, i.e., g(T ) is a vertex of Q k+1 (S).

If we turn around g(T ) in clockwise direction starting from τ 0 until we reach an edge of Q k+1 (S), we only encounter type-2 triangles (if any). As in (b), it follows that the edge of Q k+1 (S) that we reach belongs to the same domain as the edge [g(P 0 ∪ {r 0 }), g(P 0 ∪ {s 0 })] of τ 0 , i.e., to the domain of P 0 ∪ {r 0 , s 0 } = T ∪ {s 0 }. Thus, the edge that we reach is of the form [g(T ), g((T \ {u}) ∪ {s 0 })], with u ∈ T . Since, by construction, g((T \ {u}) ∪ {s 0 }) follows g(T ) in counterclockwise direction on ∂Q k+1 (S), it results from Proposition 6(ii) that (us 0 ) -∩ S = T \ {u}. This implies that (us 0 ) is a common inner tangent of conv(T ) and of conv(S \ T ), with u a vertex of conv(T ) and s 0 a vertex of conv(S \ T ). In the same way, the edge of ∂Q k+1 (S) that we reach when we turn in counterclockwise direction around g(T ) starting from τ m belongs to the same domain as the edge [g(P m ∪ {r m }), g(P m ∪ {t m })], i.e., to the domain of T ∪ {t m }. Thus, there exists v ∈ T such that g((T \ {v}) ∪ {t m }) is the vertex of Q k+1 (S) that precedes g(T ) in counterclockwise direction on ∂Q k+1 (S). Again, we have (t m v) -∩ S = T \ {v}, which implies that (t m v) is the second common inner tangent of conv(T ) and of conv(S \ T ), with v a vertex of conv(T ) and t m a vertex of conv(S \ T ). Furthermore, if t m = s 0 , conv(T ) ⊂ (s 0 t m ) + . Notice finally that t m and s 0 must be distinct. Indeed, otherwise, the two edges [g(T ), g((T \ {u}) ∪ {s 0 })] and [g(T ), g((T \ {v}) ∪ {t m })] of Q k+1 (S) would belong to the same domain. Since the domains are convex, all triangles around g(T ) would belong to this domain. This is impossible since, from (a), g(T ) is the vertex of at least one type-1 triangle. Thus, it follows from (b) and (c), that the link L of T is a simple oriented open polyline that connects s 0 to t m .

Constrained triangulations of links

All that remains to be done to apply Algorithm 1 to convex configurations is to define the notion of constrained triangulation for links like the ones characterized by Proposition 10. If L is a simple closed polyline, a constrained triangulation of L is classically defined as a triangulation of the vertices of L that admits every edge of L as an edge and that is restricted to disk(L). If L is reduced to a segment (or to two overlapping segments with opposite orientations), the unique constrained triangulation of L degenerates to L.

We extend this definition to a simple open oriented polyline L whose endpoints are vertices of conv(L): A constrained triangulation of L is a triangulation of the vertices of L that admits every edge of L as an edge and that is restricted to the subset of conv(L) on the left side of L (see Figure 10). Again the triangulation may degenerate to L when L is a segment or when conv(L) is on the right side of L, implying that L is included in ∂conv(L). The following lemma will serve in Section 5.3 to characterize constrained triangulations of links in maximal families of convex configurations. Lemma 1. Let T be a nonempty subset of S and let L be a simple closed polyline that satisfies the following three properties: 1. L has at least three vertices, 2. every vertex of L is in S \ T , 3. for every edge [u, v] of L, (T, {u, v}) is a convex pair of S. Let r, s, t be three distinct vertices of L such that the triangle rst is included in disk(L).

(i) The pair (T, {r, s, t}) is a convex pair of S. (ii) If (P, Q) is a convex pair of S such that T ⊆ P and if (P, Q) is compatible with every convex pair (T, {u, v}) of S such that [u, v] is an edge of L, then (P, Q) is also compatible with (T, {r, s, t}).

Proof. Let T L be a constrained triangulation of L that admits rst as a triangle. It is well known that any triangulation of a simple polygon admits a triangle (generally called an ear ) that has two edges on the boundary of the polygon.

Let abc be such a triangle of T L with [a, b] and [b, c] the edges that belong to L.

(a) First, we prove that the pair (T, {a, b, c}) satisfies (i), i.e., that (T, {a, b, c}) is a convex pair of S. Since, by hypothesis, (T, {a, b}) and (T, {b, c}) are convex pairs of S, c does not belong to conv(T ∪ {a, b}) and a does not belong to conv(T ∪ {b, c}). Thus, a and c are extreme points of T ∪ {a, b, c}.

We show now that b is also an extreme point of T ∪ {a, b, c}, i.e., b does not belong to conv(T ∪ {a, c}). Since T is nonempty, conv(T ∪ {a, c}) can be decomposed into triangles whose vertices are in T ∪ {a, c} and that all have a same point p ∈ T as a vertex. These triangles are of the form pqq , with either {q, q } = {a, c}, or {q, q } ⊂ T ∪ {a}, or {q, q } ⊂ T ∪ {c}. The latter two types of triangles are respectively contained in conv(T ∪ {a}) and in conv(T ∪ {c}). These triangles cannot contain b, since (T, {a, b}) and (T, {b, c}) are convex pairs, which implies that b is an extreme point of both T ∪ {a, b} and T ∪ {b, c}. To complete the proof that (T, {a, b, c}) is a convex pair of S, it now suffices to prove that conv(T ∪{a, b, c})∩S = T ∪{a, b, c}. As above, for any p ∈ T ∪{b}, conv(T ∪ {a, b, c}) equals conv(T ∪ {a, b}) ∪ conv(T ∪ {b, c}) ∪ conv({p, a, c}). If conv(T ∪ {a, b, c}) contains a point q of S \ (T ∪ {a, b, c}), this point can only be in the interior of conv(p, a, c) = pac, since (T, {a, b}) and (T, {b, c}) are convex pairs of S and since q, a, c are not collinear. Again, we can find an edge [u, v] of L such that q ∈ conv(p, u, v) ⊆ conv(T ∪ {u, v}), which is impossible.

(b) Now, we prove by contrapositive that (T, {a, b, c}) satisfies (ii), i.e., (ii) holds when (T, {r, s, t}) = (T, {a, b, c}). If a convex pair (P, Q) is incompatible with (T, {a, b, c}) but is compatible with (T, {a, b}) and with (T, {b, c}), Definition 5 leads to:

relint(conv((T ∪ {a, b, c}) \ P )) ∩ relint(conv((P ∪ Q) \ T )) = ∅, (3)
relint(conv((T ∪ {a, b}) \ P )) ∩ relint(conv

((P ∪ Q) \ T )) = ∅, (4)
relint(conv((T ∪ {b, c}) \ P )) ∩ relint(conv

((P ∪ Q) \ T )) = ∅. (5)
Neither c nor a can belong to P , otherwise (1) contradicts either (2) or (3). Thus, setting R = (T ∪ {b}) \ P , the preceding relations become:

relint(conv(R ∪ {a, c})) ∩ relint(conv((P ∪ Q) \ T ) = ∅, (6) relint
(conv(R ∪ {a})) ∩ relint(conv((P ∪ Q) \ T ) = ∅, (7) relint
(conv(R ∪ {c})) ∩ relint(conv((P ∪ Q) \ T ) = ∅. ( 8
)
If R is empty, T is obviously contained in P , and we are done. Otherwise, as in (a), we have, for every point p ∈ R,

conv(R ∪ {a, c}) = conv(R ∪ {a}) ∪ conv(R ∪ {c}) ∪ conv({p, a, c}). (9)
Thus, when relint(conv((P ∪ Q) \ T )) cuts relint(conv(R ∪ {a, c})), it either cuts relint(conv(R ∪ {a})), or relint(conv(R ∪ {c})), or relint(conv({p, a, c})), or the intersection is included in the boundaries of these convex hulls.

From ( 7) and ( 8), the two first cases are impossible. Consider the case where relint(conv((P ∪ Q) \ T )) cuts relint(conv({p, a, c})), the interior of the triangle pac. Since [p, a] ⊆ conv(R ∪ {a}) and [p, c] ⊆ conv(R ∪ {c}), it follows from [START_REF] Hansen | Adaptive parametrization of multivariate B-splines for image registration[END_REF] and (8) that neither ]p, a[ nor ]p, c[ can be traversed by relint(conv((P ∪ Q) \ T ). Therefore, at least one vertex q of conv((P ∪ Q) \ T ) must belong to conv({p, a, c}) \ {a, c}. Now, conv({p, a, c}) ⊆ conv(T ∪ {a, b, c}) and, from (a), conv(T ∪ {a, b, c}) contains no point of S \ (T ∪ {a, b, c}). Since q ∈ (P ∪ Q) \ T , it follows that q ∈ {a, b, c}. Hence, q = b. Furthermore, since b is an extreme point of T ∪ {a, b, c}, q = b cannot be in the interior of the triangle pac. Thus, we have q = p = b.

We are left with the case where the intersection A of relint(conv((P ∪Q)\T )) with relint(conv(R ∪ {a, c})) is included in the union of the boundaries of the convex hulls conv(R ∪ {a}), conv(R ∪ {c}), and conv({p, a, c}), but cuts the interior of none of these convex hulls. Since A is convex, A is either an open line segment or a point. Furthermore, since R ∪ {a, c} contains at least three non collinear points, the dimension of A equals the dimension of conv((P ∪ Q) \ T ).

Hence, if A is reduced to a point q, (P ∪ Q) \ T is also reduced to q. Since S has no three collinear points, q cannot belong to an open edge of conv(R ∪ {a}), conv(R ∪ {c}), or conv({p, a, c}). Thus, q is a vertex of one of these convex hulls. Now, since q is in the interior of conv(R ∪ {a, c}), it follows from (9) that the neighborhood of q is covered by conv(R ∪ {a}), conv(R ∪ {c}), and conv({p, a, c}). Since these three sets are strictly convex and since q belongs to the interior of none of them, q must be a common vertex of all of them. Hence, q belongs to (R ∪ {a}) ∩ (R ∪ {c}) ∩ {p, a, c}. Thus, q equals p and belongs to R = (T ∪ {b}) \ P . Since q belongs also to (P ∪ Q) \ T , we have q = p = b.

We deal now with the case where A is a line segment. Since S admits no three collinear points, (P ∪ Q) \ T contains exactly two points q and q , A is an edge of one of the convex hulls conv(R ∪ {a}), conv(R ∪ {c}), conv({p, a, c}), and q, q are the endpoints of this edge. As before, since these convex hulls cover the neighborhood of A, [q, q ] is a common edge of at least two of them. Now, conv(R ∪ {a}) and conv(R ∪ {c}) cannot have [q, q ] as a common edge since b is the only possible common point of R ∪ {a}, R ∪ {c}, and (P ∪ Q) \ T . If [q, q ] is a common edge of conv(R ∪ {a}) and of conv({p, a, c}), we have {q, q } = {p, a}. Since b and a are the only possible common points of R ∪ {a} and (P ∪ Q) \ T , we have p = b. In the same way, if [q, q ] is a common edge of conv(R ∪ {c}) and of conv({p, a, c}), we have again p = b.

Thus, for every point p in R = (T ∪ {b}) \ P , we have p = b, implying that T ⊆ P . This proves that (T, {a, b, c}) satisfies (ii).

(c) We finally prove that (T, {r, s, t}) satisfies (i) and (ii). From (a) and (b), it is the case if rst = abc. If rst = abc L has at least four vertices. Let (P, Q) be a convex pair of S such that T P and that is compatible with every convex pair (T, {u, v}) of S such that [u, v] is an edge of L. From (a), (T, {a, b, c}) is a convex pair of S and is compatible with (P, Q). From Proposition 1, the sub-pair (T, {a, c}) of (T, {a, b, c}) is also a convex pair of S and, from Proposition 2, (T, {a, c}) is compatible with (P, Q). Thus, the polyline L = (L \ ([a, b] ∪ [b, c])) ∪ [a, c] satisfies the same three properties as L. Furthermore, rst is a triangle of the constrained triangulation T L \ abc of L . By induction on the number of vertices of L, it follows that (T, {r, s, t}) satisfies (i) and (ii).

Validity of Algorithm 1

We can now prove that Algorithm 1 constructs maximal families of compatible convex configurations of S. Theorem 8. If Algorithm 1 is applied to a maximal family ∆ k of compatible convex k-configurations of S, then it generates a maximal family ∆ k+1 of compatible convex (k + 1)-configurations of S.

Proof. Let ∆ k+1 be a family of configurations constructed by Algorithm 1 when it is applied to a maximal family ∆ k of compatible convex k-configurations of S.

(i) We first prove that the configurations in ∆ k+1 are convex, are pairwise compatible, and are compatible with ∆ k . By Algorithm 1, for every configuration (T, {r, s, t}) of ∆ k+1 , T is a vertex of ∆ k . Let L be the link of T in ∆ k , and let T L be the constrained triangulation of L constructed by Algorithm 1 when it generates ∆ k+1 . The triangle rst is a triangle of T L .

(i.1) We first show that, for every outer edge [u, v] of T L , i.e., an edge of T L that is not shared by two triangles of T L , (T, {u, v}) is a convex pair of S compatible with ∆ k .

Since T L contains at least one triangle, it follows from Proposition 10 that, if T is not a (k + 1)-set of S, L is a simple closed polyline of at least three vertices. Thus, the outer edges of T L are the edges of L.

If T is a (k+1)-set of S, L is a simple open oriented polyline whose endpoints are vertices of conv(S \ T ). Since all vertices of L belong to S \ T , the endpoints of L are vertices of conv(L). Let p and p be the first and the last endpoint of L respectively, and let L be the oriented polyline that connects p to p in counterclockwise direction on ∂conv(L), i.e., L is the part of ∂conv(L) in (pp ) + . By definition of constrained triangulations of open oriented polylines, the outer edges of T L are the edges of L ∪ L . Obviously, the lines L and L cannot cross, but may meat at common vertices and may have common edges with opposite orientations.

Whether T is a (k + 1)-set of S or not, from Definition 10, every edge [u, v] of L is the link of T in a convex configuration (P, {w, u, v}) of ∆ k such that P ∪ {w} = T . By Proposition 1, the sub-pair (T, {u, v}) of (P, {w, u, v}) is a convex pair of S and, from Proposition 2, (T, {u, v}) is compatible with ∆ k .

If T is a (k + 1)-set of S, from Proposition 10, the endpoints p and p of L belong to the common inner tangents of conv(S \ T ) and conv(T ), and are such that conv(T ) ⊂ (pp ) + . Thus, for every point t ∈ T and for every point x ∈ ∂conv(S \ T ) ∩ (pp ) + , the half-line [tx) radiating from t penetrates conv(S \ T ) in x (see Figure 12). Therefore, [tx) intersects L in at least one point y, possibly coinciding with x. Let [q, q ] be one of the closed edge of L that contain y (there are two such edges if x is a vertex of L). Clearly, x belongs to conv({t, q, q }) ⊆ conv(T ∪ {q, q }). Now, from what precedes, (T, {q, q }) is a convex pair of S, implying conv(T ∪ {q, q }) ∩ S = T ∪ {q, q }. Thus, if x is a point of S, it must be either q or q . Consequently, every vertex of conv(S \T ) in (pp ) + is a vertex of L. Hence, ∂conv(S \ T ) ∩ (pp ) + equals ∂conv(L) ∩ (pp ) + , i.e., L is the polyline that connects p to p in counterclockwise direction on ∂conv(S \ T ). Therefore, for every oriented edge [u, v] of L , (uv) -∩ S = T . From Proposition 7, (T, {u, v}) is a convex pair of S and is compatible with ∆ k .

(i.2) Whether T is a (k + 1)-set or not, rst is a triangle of a constrained triangulation of the boundary C of a bounded connected component of R 2 \ (L ∪ L ) (we set L = ∅ when T is not a (k + 1)-set of S). The boundary C is a simple closed polyline of at least three vertices and, from (i.1), for every edge [u, v] of C, (T, {u, v}) is a convex pair of S compatible with ∆ k . It follows from Lemma 1(i), that (T, {r, s, t}) is a convex configuration of S. Furthermore, for every pair

(P, Q) of ∆ k , we have k = |P | < |T | = k + 1.
It follows that T is not included in P and therefore, from Lemma 1(ii), that (P, Q) is compatible with (T, {r, s, t}).

This shows that the configurations in ∆ k+1 are convex and are compatible with ∆ k .

(i.3) Now, we prove that every configuration (T , {r , s , t }) of ∆ k+1 distinct from (T, {r, s, t}) is compatible with (T, {r, s, t}). From (i.2), (T , {r , s , t }) is compatible with ∆ k . From Proposition 2, for every edge [u, v] of C, (T , {r , s , t }) is also compatible with (T, {u, v}), since (T, {u, v}) is a sub-pair of a configuration of ∆ k . If T = T , since |T | = |T |, T is not included in T . It follows from Lemma 1, that (T , {r , s , t }) is compatible with (T, {r, s, t}). If T = T , rst and r s t are two triangles of the constrained triangulation T L . Therefore, their interiors are disjoint, i.e., relint(conv((T ∪ {r, s, t}) \ T )) ∩ relint(conv((T ∪ {r , s , t }) \ T )) = ∅. This implies that (T, {r, s, t}) and (T, {r , s , t }) are compatible.

It follows that the configurations of ∆ k+1 are pairwise compatible.

(ii) Now, we show that ∆ k+1 is a maximal family of compatible convex (k + 1)-configurations. Let T be the set composed of the type-2 centroid triangles associated with the configurations in ∆ k and of the type-1 centroid triangles associated with the configurations in ∆ k+1 .

(ii.1) We first show that every edge of a type-1 triangle of T is either an edge of another triangle of T or an edge of Q k+2 (S).

Let τ be a type-1 triangle of T and let (T, {r, s, t}) be the convex configuration of ∆ k+1 with which it is associated, i.e., τ = g(T ∪{r})g(T ∪{s})g(T ∪{t}). By construction, T is a vertex of ∆ k . Denoting by L the link of T in ∆ k , rst is a triangle of the constrained triangulation T L of L constructed by Algorithm 1. Thus, every edge of rst, say st, is either an edge of another triangle r st of T L or an outer edge of T L . In the first case, the edge [g(T ∪ {s}), g(T ∪ {t})] of τ is also an edge of the triangle g(T ∪ {r })g(T ∪ {s})g(T ∪ {t}) of T associated with (T, {r , s, t}). In the second case, from (i), [s, t] is either an edge of L or an edge of ∂conv(S \ T ) such that (st) -∩ S = T . If [s, t] is an edge of L, [s, t] is the link of T in a configuration of ∆ k and this configuration is necessarily of the form (T \ {w}, {w, s, t}), with w ∈ T . The edge [g(T ∪ {s}), g(T ∪ {t})] of τ is then also an edge of the type-2 centroid triangle g((T \ {w}) ∪ {w, s})g((T \ {w}) ∪ {w, t})g((T \ {w}) ∪ {s, t}) of T associated with (T \ {w}, {w, s, t}). Finally, in the case (st) -∩ S = T , the edge With the result of this theorem, we are now able to prove the following conjecture.

Conjecture of Liu and Snoeyink. If Algorithm 1 is first applied to a family of 0-configurations that induces a triangulation of S, and if the algorithm is then iteratively applied to the family of configurations generated by the algorithm itself, then all constructed families are valid.

Proof. Let ∆ 0 be a family of 0-configurations that induces a triangulation T of S, i.e., ∆ 0 is the set of configurations (∅, {r, s, t}) with rst a triangle of T . Since rst contains no point of S \ {r, s, t}, (∅, {r, s, t}) is a convex configuration of S. If rst and r s t are two distinct triangles of T , they have disjoint interiors and therefore, from Definition 5, the 0-configurations (∅, {r, s, t}) and (∅, {r , s , t }) are compatible. Therefore, ∆ 0 is a family of compatible convex configurations of S and, from Proposition 3(ii), there exists a maximal family F of compatible convex subsets of S compatible with ∆ 0 . Now, by Definition 8, the triangles of T are the type-1 centroid triangles associated with the configurations in ∆ 0 . Since T is a triangulation of conv(S) = Q 1 (S), it follows from Theorem 5(i) that ∆ 0 is the family of all convex 0-configurations of S compatible with F. Therefore, from Corollary 1, ∆ 0 is a maximal family of compatible convex 0-configurations.

Thus, from Theorem 8, if Algorithm 1 is first applied to ∆ 0 , and is then iteratively applied to the families ∆ k generated by the algorithm itself, Algorithm 1 constructs maximal families of compatible convex configurations. From Theorem 3, this proves that the configurations constructed by the algorithm are valid.

Conclusion

In the bivariate setting, the families of convex configurations introduced here generalize the family of Delaunay configurations of Neamtu. Hence, convex configurations enable to generate a wider variety of bivariate splines. As shown by Liu and Snoeyink [START_REF] Liu | Quadratic and cubic B-splines by generalizing higherorder Voronoi diagrams[END_REF][START_REF] Liu | Computations of Delaunay and higher order triangulations, with applications to splines[END_REF], among them are two well known variety of splines: the Zwart-Powell element, which is a quadratic box spline [START_REF] De Boor | Box Splines[END_REF], and the triangular Bézier patch [START_REF] Prautzsch | Bézier and B-Spline Techniques[END_REF].

Using the fact that the edge matching property of Delaunay configurations extends to higher dimensions as a facet matching property, Neamtu proved that Delaunay configurations are valid in every dimension, i.e., the simplex spline space over Delaunay configurations reproduces all multivariate polynomials [START_REF] Neamtu | Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay[END_REF]. The question that arises is if the results in the present paper also generalize to higher dimensions.

The definition of convex configurations can be extended in d dimensions by just replacing, in Definition 3, |Q| = 3 by |Q| = d + 1. Hence, a d-dimensional convex configuration of S is a pair (P, Q) of disjoint subsets of S such that conv(P ∪ Q) ∩ S = P ∪ Q, Q is a subset of the extreme points of P ∪ Q, and |Q| = d + 1. The definition of compatibility extends as such to higher dimensions: Two distinct convex pairs (P, Q) and (P , Q ) of S are compatible if relint(conv((P ∪ Q) \ P )) ∩ relint(conv((P ∪ Q ) \ P )) = ∅. It is not hard to check that Delaunay configurations are compatible convex configurations in all dimensions.

Centroid triangles extend to centroid polytopes in the following way. For every i ∈ {1, . . . , d}, the type-i centroid polytope associated with the convex configuration (P, Q) is the convex polytope whose vertices are the centroids g(P ∪ R), with R ⊂ Q and |R| = i. Notice that only the type-1 and the type-d polytopes are simplices. It is not hard to show that the centroid polytopes of type 1, . . . , d associated with the configurations of order k + 1, . . . , k + d respectively have pairwise disjoint interiors. The difficulty is to prove that these polytopes cover the (k + d -1)-set polytope of S, which is the convex hull of all (k + d -1)-point subsets of S. This result, which has already been proved for Delaunay configurations [START_REF] Schmitt | k-set polytopes and order-k Delaunay diagrams[END_REF], would enable to extend the facet matching property to convex configurations and would imply that maximal families of convex configurations are valid in the multivariate setting.

Centroid triangulations turn out to be a useful tool in different contexts. They would deserve to be studied for themselves, even in the plane.

Figure 1 :

 1 Figure 1: Order-2 B-splines defined over subsets of 4 consecutive knots of the set S = {t 0 , . . . , t 6 }.

  If a and b are two distinct points in the plane, (ab) is the oriented straight line from a to b, [a, b] is the closed segment connecting a and b, and ]a, b[ is the open segment. For any oriented straight line , + and -denote the open half planes respectively on the left and on the right of . For a Jordan curve γ, disk(γ) denotes the bounded open component of R 2 \γ.

= 3 MFigure 2 :

 32 Figure 2: A set of five knots in R 2 (identified with the plane z = 0 of R 3 ) and the order-2 simplex spline defined over this set.

Figure 4 :

 4 Figure 4: (a) If two convex pairs (P, Q) and (P , Q ) admit two separating curves γ and γ that properly intersect in two points, then the subsets (P ∪ Q) \ P and (P ∪ Q ) \ P are on both sides of (or on) the straight line l containing γ ∩ γ . The points of these subsets that are on l are the points of Q ∩ Q . The set P ∩ P is in the open area disk(γ) ∩ disk(γ ). (b) The relative interiors are necessary in Definition 5 (i) to ensure that the pairs (∅, {a, b, c}) and (∅, {a, b}) are considered to be compatible.

Figure 5 :

 5 Figure 5: The order-2 Voronoi diagram (full lines) and the dual order-2 centroid Delaunay triangulation (dashed lines) of S = {1, . . . , 6}. The gray Voronoi region is the set of points of the plane that are closer to 3 and 5 than to any other point of S. Its dual vertex in the order-2 centroid Delaunay triangulation is the centroid g({3, 5}).

Theorem 4 .

 4 If no four points in S are cocircular and if k ∈ {0, . . . , n -3}, the number of Delaunay k-configurations of S equals

Proposition 6 .

 6 (i) The vertices of Q k (S) are the centroids of the k-sets of S. Distinct k-sets have distinct centroids. The centroid of any other k-point subset of S is in the interior of Q k (S).

1 (Figure 6 :

 16 Figure 6: A triangulation T 4 of the 4-set polygon of the set S = {1, . . . , 7}. The type-1 centroid triangles (in white) are associated with convex 3-configurations of S and the type-2 centroid triangles (in gray) are associated with convex 2-configurations of S. The type-2 centroid triangles form convex clusters called domains.

Figure 7 :

 7 Figure 7: (a) The triangulation of S = {1, . . . , 7} induced by the convex 0-configurations (∅, {1, 7, 2}), (∅, {1, 6, 7}), (∅, {1, 5, 6}), (∅, {2, 7, 3}), (∅, {3, 7, 4}), (∅, {4, 7, 6}), and (∅, {4, 6, 5}).(b) One can check that the nine convex 1-configurations ({1}, {7, 5, 6}), ({2}, {1, 7, 3}), ({3}, {2, 7, 4}), ({4}, {7, 6, 3}), ({6}, {4, 7, 5}), ({6}, {1, 5, 7}), ({7}, {4, 3, 2}), ({7}, {4, 2, 1}), and ({7}, {4, 1, 6}) form a family ∆ 1 of compatible convex 1-configurations of S. The dotted polygon is the link of {4, 7} in ∆ 1 and the full polyline oriented from 5 to 2 is the link of {1, 7} in ∆ 1 .

Figure 8 :

 8 Figure8: The order-1 centroid triangulation T 1 (thin dashed lines) and the order-2 centroid triangulation T 2 (thin full lines) induced by the families ∆ 0 and ∆ 1 of compatible convex 0and 1-configurations of the caption of Figure7. The four sick dashed segments are the edges opposite to the vertex g({4, 7}) in the type-1 centroid triangles (white) around g({4, 7}) in T 2 . These edges are homothetic images of the edges of the link of {4, 7} in ∆ 1 (see Figure7(b)). The three sick full segments are the homothetic images of the edges of the link of {1, 7} in ∆ 1 .

Proposition 10 .

 10 Let ∆ k be a maximal family of compatible convex k-configurations of S. Let T be a vertex of ∆ k and let L be the link of T .(i) If T is not a (k + 1)-set of S then -either T is the vertex of precisely two configurations of ∆ k and L is composed of two overlapping line segments with opposite orientations, -or T is the vertex of at least three configurations of ∆ k and L is a simple closed oriented polyline.(ii) If T is a (k + 1)-set of S then L is a simple open oriented polyline. The first point p and the last point p of L are the vertices of conv(S \ T ) on the common inner tangents of conv(S \T ) and conv(T ) such that conv(T ) ⊂ (pp ) + .

Figure 9 :

 9 Figure 9: Centroid triangles around a vertex g(T ) of Q k+1 (S). The type-1 triangles are in white.

Figure 10 :

 10 Figure 10: A constrained triangulation of the open oriented polyline that links p to p .

  Thus, if b belongs to conv(T ∪ {a, c}), it must belong to the triangle pac without being on its edges [p, a] ⊆ conv(T ∪ {a}), [p, c] ⊆ conv(T ∪ {c}), and [a, c] since a, b, c are not collinear. Hence, the straight line (pb) cuts the open segment ]a, c[ in a point x that is in disk(L), by construction (see Figure 11). The half-line of (pb) out of x and that does not contain p cuts L in at least one edge [u, v] (possibly coinciding with [a, c]). Thus, we have b ∈ conv({p, u, v}) ⊆ conv(T ∪ {u, v}). This is impossible since (T, {u, v}) is a convex pair of S and since b / ∈ T ∪ {u, v}. It follows that b is an extreme point of T ∪ {a, b, c}.

Figure 11 :

 11 Figure 11: Illustration for the proof of Lemma 1.

Figure 12 :

 12 Figure 12: From proof of Theorem 8, every vertex of ∂conv(S \ T ) ∩ (pp ) + belongs to L.