On Characterization of Poised Nodes for a Space of Bivariate Functions ()
1. Introduction
Consider the interpolation problem with a finite dimensional space of univariate func- tions S and a set of knots
that is for a given data
find a function
satisfying the conditions
(1)
We say that the set of knots is poised for S if for any data
there is a unique function
satisfying the conditions (1). A necessary condition of the poisedness is

There are several cases of spaces S of univariate functions for which we have a characterization of all poised sets.
Suppose that
is the space of polynomials of degree at most n. We have that
Then, according to the Lagrange theorem, all sets of knots
are poised.
Now suppose that
is the space of spline functions of order n and
are the knots of the space (see, e.g., [1] ). Here
means that s is piecewise polynomial function of degree at most
s vanishes outside of the segment
and s belongs to the differentiability class
We have that
and the set of interpolation knots
is poised if and only if the following conditions are satisfied:
![]()
This result is due to Schoenberg and Whitney [2] [3] . In the univariate case there are also several characterization results concerning the trigonometric interpolation.
In contrast with this there are no such results in the bivariate case. As an exception one may consider only the Pascal classic theorem, in the interpolation theory inter- pretation (see, e.g., [4] ). To present it let
be the space of bivariate polynomials of total degree at most 2. We have that
Let also
be the space of bivariate linear functions,
Then consider any set of 6 nodes
in the plane. Construct 3 new nodes as follows:
![]()
where
is the line passing through the nodes
and
Then according to the Pascal theorem the 6 nodes
are lying in a conic if and only if the 3 nodes
are collinear. To arrange the case connected with the parallel pairs of lines one may replace the plane with the projective one. The interpolation version of this result is:
Theorem 1.1 (Pascal) Any 6 nodes
in the plane are poised for
if and only if the set of respective 3 nodes
is poised for ![]()
Note that the latter poisedness condition with
merely means that
are not collinear.
Next we are going to introduce the space of bivariate functions we will consider in this paper. For this we need some preliminaries.
Let us define a strip of triangles. Fix a sequence of points in the plane
![]()
for the vertices of triangles. Then consider the n triangles
(2)
Note that by a triangle we mean the closed set bounded by the sides of the triangle. The sequence of the triangles
![]()
makes a triangulation of the following strip (see Figure 1)
![]()
Sometimes it is convenient to call itself
a strip, too.
Here we require that the intersection of any neighboring triangles
and
is the common side
any pair of triangles
and
have a single common point which is the vertex
and all the other pairs of the triangles are disjoint.
It is easily seen that the sides
together with the sides
and
form the boundary of the strip
(see Figure 1). We call these sides boundary sides. The remaining sides of the triangles are called interior sides of the strip. Let us call also the sides
and
the left and right (boundary) sides of the strip
respectively, and denote
![]()
For a triangle
given in (2) we call the sides
and
the left and right sides of it, respectively.
Denote by
the linear space of continuous piecewise linear functions on
More precisely,
means that
i) ![]()
ii) ![]()
Here
means the restriction of s on D.
Definition 1.2 A set of nodes
is called poised for the space
if for any data
the interpolation problem
(3)
has exactly one solution ![]()
Let us denote the interpolation problem (3) by ![]()
The aim of this paper is the characterization of all poised sets for the space
The following is a necessary condition of the poisedness:
(4)
To prove this consider the fundamental functions of the interpolation
defined by the interpolation conditions
![]()
where
is the symbol of Kronecker.
Obviously the fundamental functions are linearly independent and for the solution of the interpolation problem (3) we have the following formula of Lagrange:
![]()
Thus, the fundamental functions form a basis for
and we get (4).
Now, let us show that the set of vertices
is a poised set for
Indeed, having the values of a linear function at the vertices of a triangle
we recover it in a unique way on the triangle. On the other hand it is easily seen that the recovered piecewise linear function is continuous on
Thus, the dimension of
equals to the number of the vertices in the strip ![]()
(5)
In view of (4) we obtain that any poised set
for the space
consists of
nodes:
(6)
Let us call interpolation problem
satisfying this condition exact. In the cases
and
we call the problem
underdetermined and over- determined, respectively.
Denote by
![]()
the fundamental polynomials with respect to the poised set
. They form a basis for the space
Thus we have the following representation for any piecewise linear function ![]()
![]()
In view of this representation the interpolation problem (3) reduces to m linear equations with
unknowns, which are the values a piecewise linear function at the vertices
. Hence an exact interpolation problem
is poised if and only if the following Vandermonde determinant does not vanish:
(7)
where
![]()
Thus our main problem can be formulated in terms of Vandermonde determinant in the following way:
Characterize all exact sets
for which the Vandermonde determinant does not vanish, i.e., (7) holds.
The following two propositions are basic Linear Algebra facts.
Proposition 1.3 Given an exact problem
Then each of the following con- ditions is equivalent to the poisedness of
:
i) All fundamental functions
exist.
ii) ![]()
Proposition 1.4 Given a problem
Then the following hold:
i) If the problem is underdetermined then there is a function
such that
![]()
ii) If the problem is overderdetermined then there is a node in
for which no fundamental function exists.
2. Subproblems
For a given strip
denote by
the following part of it
![]()
For a problem
denote by
the subproblem with the function space
and the set of nodes
i.e.,
![]()
Problems with Boundary Conditions
Denote by
the linear space of continuous piecewise linear functions on
vanishing at the left (boundary) side of the strip
, i.e.,
![]()
In the similar way one can define the space of functions vanishing at the right side of the strip
i.e.,
![]()
One may define also the space of functions vanishing at the both left and right sides of the strip
i.e.,
![]()
By counting the number of vertices of the strip where a function from the space may differ from
we get, in the same way as in the proof of (5), that
![]()
Denote the interpolation problems with the spaces
and a node set
by
respectively.
As we will see below the poisedness of interpolation problems with boundary con- ditions readily can be reduced to the previous general interpolation problems by just adding two nodes in the left or/and right sides of the strip.
For this purpose it is convenient to use the following notation for the strip ![]()
![]()
where
and
are the two vertices of ![]()
![]()
where
and
are the two vertices of
Denote also
![]()
Let us call two interpolation problems equivalent if both they are poised or both they are not poised. By using Proposition 1.3, ii), we readily get
Proposition 2.1 The folllwing pairs of interpolation problems are equivalent:
and ![]()
and ![]()
and ![]()
Note that in the subproblem
we have that
![]()
where
and
are the two vertices of
The situation is similar with the sets
and ![]()
3. Reductions of Interpolation Problems
Below we bring a main theorem regarding the reduction of an interpolation problem having an exact or overdetermined subproblem.
Theorem 3.1 Suppose that
is an exact problem where the strip
consists of n triangles and
is a subproblem, where
.
Then the following hold.
i) If the subproblem
is exact and not poised, or overdetermined, then the problem
is not poised.
ii) If the subproblem
is poised then the problem
is poised if and only if the both following two reduced problems
(8)
are exact and poised.
Note that in the cases
and
we have just one reduced problem instead of two.
Proof. Suppose first that the subproblem
is exact and not poised, or overdetermined. Then, in view of Propositions 1.3, i), and 1.4, ii), there is a node
which does not have a fundamental function. Then, evidently the same node A does not have a fundamental function for the whole node set
too. Hence, in view of Proposition 1.3, i), we get that the problem
is not poised.
Now consider the case when the subproblem
is poised.
Let us assume that the both reduced problems in (8) are poised. Then let us prove that the problem
is poised, too. Notice first that the problem
is exact. Thus, by following Proposition 1.3, ii), assume that
Now, since the subproblem
is poised, we conclude that s vanishes on the triangles
Therefore s vanishes at the right side of the triangle
and at the left side of the triangle
Thus we have that
and
Finally, since the problems in (8) are poised, we obtain that s vanishes on the triangles
and
Hence s vanishes on all triangles of ![]()
Next let us assume that the problem
is poised and prove that the both reduced problems in (8) are poised, too. Let us show first that these reduced problems are exact. There are
and
triangles in the reduced problems (8), respectively. Thus for exactness we need
and
nodes, respectively, altogether
nodes. It is easily seen that indeed, in two mentioned problems together we have that many nodes. Indeed, this is the number of the nodes in
minus the number of the nodes in
and plus 4, i.e., ![]()
Latter
nodes come from the added nodes in the boundary in the node sets
and
.
Now, assume by way of contradiction that a subproblem in (8) is not exact. Therefore one of the subproblems, say the first problem in (8), is underdetermined, and another is overdetermined. Then, in view of Proposition 1.4, i), there is a function
such that
(9)
Thus s here vanishes on
and, since of “+2”, also on the right side of the triangle
Now let us extend this function s from
till the whole strip
by defining it to be 0 on the triangles
Denote by
the extended function. Then it is easily seen that
and
This, in view of Proposition 1.3, ii), means that the problem
is not poised, which contradicts our assumption.
Finally, let us show that the both reduced problems in (8) are poised. Assume by way of contradiction that one of them, say the first, is not poised. Since it is exact, we can use Proposition 1.3, ii), to get that there is a function
such that the relation (9) is satisfied. From here we continue in the same way as in the above step, after the relation (9).
4. The Basic Interpolation Problems
Let us denote by “3” the problem with a strip consisting of a triangle and at least three nodes inside. The respective basic problem, denoted briefly by “
”, is a “3” problem with exactly three nodes, which are non-collinear.
Then, let us denote by “
” the problem with a strip consisting of two triangles and exactly two nodes in each of them. Note that in this case no node can lie in the interior side of the strip. We call a problem “
” basic and denote it by “
” if in each triangle the line passing through the two nodes there does not intersect the other triangle. Note that in the case of “
” problem no node can coincide with a vertex of the strip.
Next consider an interpolation problem denoted by “
” where m is the number of 1’s. This is the interpolation problem with a strip consisting of
triangles such that each of the first and the last triangles contains exactly two nodes and each of the other m triangles contains exactly a node. Note that in this case no node can be located in an interior side of the strip. We call a problem “
” basic and denote it by “
” if the line passing through the two nodes in each of the first and the last triangles does not intersect the neighboring triangle.
Note that the “
” problem can be considered as a special case of the
“
” problem, where ![]()
The Poisedness of the Basic Problems
Let us start this section with a simple lemma. Suppose that two nodes
of a node set
belong to a triangle of
Denote by
the points of intersection of the line passing through
and
with the sides of the triangle. Let us call
the intersection pair of
Denote by
the set of the nodes received from
by replacing the pair
with
there. We call the set
the line trans- formation of the set
with respect to the pair ![]()
Two node sets
and
are called line-equivalent if one of them can be obtained from the other by means of several line transformations.
Lemma 4.1 The exact interpolation problems
and
are equivalent, if the node sets
and
are line-equivalent.
Proof. In view of Proposition 1.3, ii), it suffices to verify that
(10)
where the node set
is the line transformation of the set
with respect to an appropriate pair of nodes
Now notice that (10) readily follows from the evident fact that
![]()
where
is the intersection pair of
Indeed, each side of this equiva- lence means merely that
vanishes on the line passing through
and ![]()
The proof of the following proposition contains an easy algorithm for verifying the poisedness of basic problems.
Proposition 4.2 The problems “
” and “
” are always poised.
The problem “
” where
may be poised or not, depen- ding on the configuration of nodes. Moreover, if the problem is not poised then it becomes poised after changing the location of one of the two nodes in the first or the last triangle, such that the slope of the line passing through the two nodes is changed.
Note that the case
here concerns the problem “
”
Proof. The case of “
” is obvious.
Consider the problem “
” (see Figure 2). Suppose that ![]()
and
, where
In view of Lem- ma 4.1 we may replace the node set
with the set
where
and
are the intersection pairs of the respective pairs from
Since the problem
is basic we have that the nodes
belong to the four sides of the triangles
and
which are boundary sides of the strip
one node in each side (see Figure 2). Now suppose by way of contradiction that the problem
is not poised. This in view of Proposition 1.3, ii), means that there is a function
such that
while
Then it is easily seen that
and therefore
Assume without loss of generality that
Then, since s is linear and
we get readily that
and
Now, in view of the latter condition and
we get readily that
and
Thus s assumes negative values at all the vertices of the triangle
and it vanishes at
which is a contradiction.
Finally, consider the problem “
” where
Suppose that
and
, where ![]()
Assume that the problem
is not poised. This in view of Proposition 1.3, ii), means that there is a function s such that
(11)
It is easily seen that
Indeed,
implies that s vanishes at the left side of
Then, in view of the condition
where
we conclude that
Notice that
does not belong to the left (or right) side of the triangle, since the problem is basic. Continuing this way we obtain
and thus
contradicting our assumption. In the same way we get that
(12)
By replacing s, if necessary, with a nonzero constant multiple of it, assume that
Now, in view of the condition
where
the func- tion
is determined on
Indeed, the nodes
are not collinear since the problem is basic. Hence s is determined at the left side of the second triangle
Next, we have that
where
does not belong to the left (or right) side of the triangle. Thus we get that s is determined on
Continuing this way we get that s is determined on
Now s is determined at the left side of the last triangle
By using the condition
where
we con- clude, in view of (12), that the zero set of s in
is a line
passing through
Thus if the last node
lies in this line then we have that s vanishes at
too. Hence the condition (11) holds, which, in view of Proposition 1.3, ii), means that the problem is not poised. While the condition
implies that s vanishes on
which contradicts (12) and whence (11). Thus the problem is poised in this case. This consideration makes clear also the “moreover” part of Proposition.
It is worth mentioning that if the restriction of s on the left side of triangle
has a zero (as it will happen in the case of “
”) denoted by C then the basic problem is poised, wherever the two last nodes
and
are situated. Indeed, otherwise we would have that the zero-line
of s in the last triangle passes through
and C, which contradicts the fact that the problem is basic.
5. Reductions by Basic Subproblems
5.1. Reduction by “3/B”
In the case of basic subproblem “
” we have a poised subproblem with one triangle. Thus we get from Theorem 3.1, ii), the following
Corollary 5.1 Assume that
is an exact problem, where the strip consists of n triangles. Assume also that a triangle
contains exactly 3 non-collinear nodes. Then the interpolation problem
is poised if and only if the both following two reduced problems
(13)
are exact and poised.
Note that in the cases
and
we have just one reduced problem instead of two.
5.2. Reduction by “2 + 1 + ・・・ + 1 + 2/B”
For this case we get from Theorem 3.1 the following
Corollary 5.2 Assume that
is an exact problem, where the strip consists of n triangles. Assume also that the subproblem
is basic of type “
,” where
Then the problem is not poised if the subproblem is not poised. In the case when the subproblem is poised the problem
is poised if and only if the both following two reduced problems
(14)
are exact and poised.
Note that in the cases
and
we have just one reduced problem instead of two.
Since, by Proposition 4.2, the basic problems of type “
” are always poised we get from Theorem 3.1, ii), the following
Corollary 5.3 Assume that
is an exact problem, where the strip consists of n triangles. Assume also that the subproblem
is basic of type “
”. Then the problem
is poised if and only if the both following two reduced problems
![]()
are exact and poised.
Note that in the cases
and
we have just one reduced problem instead of two.
6. Existence of a Reduction
In this section we prove that every exact problem has a subproblem of type “3”, “
”, or “
”. Next, we show that by applying line-transformations to this subproblem, we can reduce it to a basic subproblem or determine that the given exact problem is not poised. After this, by following the algorithm pointed out in the proof of Proposition 4.2, we may verify whether the basic subproblem is poised or not. If not then, in view of Theorem 3.1, i), we conclude that the given exact problem is not poised either. If the basic subproblem is poised then we may apply the respective reduction, given by Corollaries 5.1, 5.2, or 5.3. Thus we have a complete solution of the poisedness problem.
Theorem 6.1 Assume that
is an exact problem. Then it has a subproblem of type “3”, “
”, or “
”. Moreover, by using line-transformations, we either determine that the problem is not poised, or we reduce the node set
to
such that the line-equivalent problem
has a basic subproblem of type “
”, “
”, or “
”.
Proof. Suppose that a triangle contains more than 3 nodes, or exactly 3 collinear nodes. Then the problem obviously is not poised and also we have a type “3” sub- problem. If a triangle contains exactly 3 non-collinear nodes then we have a type “
” basic subproblem.
Now, let us assume that no triangle of
contains more than 2 nodes.
Step 1. Let us verify that the problem
contains a subproblem of type “
”, or “
”.
Let us throw away those triangles of
which do not contain nodes from
Let us throw away also those triangles of
which contain just one node from
located in an interior side of
By saying a node is thrown we mean that it does not belong to the remained triangles.
Notice that only a node located in an interior side of the strip can be thrown. Moreover, this can happen only if the both neighboring triangles were thrown, i.e., if it is the only node in the interior side and also the only node in the both neighboring triangles.
Assume that after this operation the connected blocks of remained triangles in
are
(15)
where ![]()
Now, let us verify that for a block here the number of nodes (from
) is greater or equal to the number of triangles plus two.
Assume by way of contradiction that for all blocks in (15) the number of nodes does not exceed the number of triangles plus one. Then we get that the number of nodes in all above connected blocks is less than or equal to the number of triangles in all connected pieces plus
, where
is the number of blocks in (15).
Next, consider the breaks, i.e., the dropped blocks. For each break we have that the number of nodes, i.e., number of the thrown nodes in the above mentioned operation, is less than or equal to the number of triangles there minus 1. Indeed, a such node (in an interior side of
) is thrown if both triangles containing it where thrown. Thus we can assign two thrown triangles to each thrown node. Also note that all the triangles assigned are different. Hence the number of nodes in all above mentioned breaks is less than or equal to the number of the triangles there minus
, since there are at least
breaks.
Thus we may conclude that the number of nodes in
does not exceed the number of triangles there plus
This contradicts the assumption that the pro- blem
is exact.
Now assume, without loss of generality, that in the first block
the number of nodes from
is greater or equal to the number of triangles there plus two. Note that if a triangle in this block contains only one node then it is not located in its left or right side, otherwise the triangle would be thrown away before.
Since no triangle contains three nodes, we get that there is a triangle in this block containing two nodes. Consider the first such triangle
i.e., a such triangle with the minimal subscript
If both the two nodes here are lying in the right side of the triangle then the next triangle
contains only these two nodes. Now notice that in the triangles from
till
the number of nodes equals to
i.e., the number of triangles here. This means that there is another triangle in the first block, following
containing two nodes, such that at least one node is not lying in the right side of the triangle.
Then consider the first such triangle
If one of the two nodes here is in the right side of the triangle then the next triangle
also contains two nodes, because otherwise it would be thrown away before. Now notice that in the triangles from
till
the number of nodes does not exceeds
i.e., the number of triangles here plus 1. This means that there is another triangle in this series, denoted by
following
containing two nodes, which do not lie in its right side. This will be the first triangle of the desired subproblem.
Now notice that in the triangles from
till
the number of nodes equals to
i.e., the number of triangles here plus 1. This means that there is another triangle in the first block, following
containing two nodes. Denote by
the first such triangle. This will be the last triangle of the desired subproblem. First notice that each triangle between
and
if there is a such, contains just one node, which, as was mentioned earlier, cannot be located in its left or right side. Therefore no node in
belongs to the left side of the triangle, since otherwise
would con- tain a node in its right side. Note also that in this case
does not coincide with
since the latter has no node in its right side.
Thus the subproblem
is of type “
”, or “
” with ![]()
Step 2. Next, by using line-transformations, we either reduce this subproblem to a basic subproblem or determine that the problem
is not poised.
First suppose that the subproblem
is of type “
”. If it is not basic then the line through the two nodes in a triangle intersects its interior side. Then by replacing these two nodes with their intersection pair we will have in the other triangle one more node, i.e., three nodes. This case was considered in the beginning of the proof.
Finally, suppose that the subproblem
is of type “
”, with
Now, if this subproblem is not basic then in the same way as in the previous case we may reduce it by line transformation to a problem of the same type, where the number of 1’s equals to
Thus we may complete readily the proof by using in- duction on m, where the first step of induction corresponds to the case
considered already.
7. Final Remarks
7.1. Some Necessary Conditions of Poisedness
Consider a problem
where the strip consists of n triangles. Denote the number of nodes from
in the triangles
by ![]()
![]()
The following proposition gives some necessary conditions of poisedness.
Proposition 7.1 Given a poised problem
where the strip consists of n triangles. Then for each k and
we have that
(16)
Moreover, in the cases
and
we have stricter inequalities:
(17)
Proof. Let us prove first the right inequality in (16):
(18)
Indeed, suppose conversely that
Then the subproblem
is overdetermined. Therefore the problem
in view of Theorem 3.1, is not poised, which is a contradiction.
In particular, we get from (18) that
(19)
Now, in view of the relations
and
we get the inequalities in the left sides in (17).
Finally, let us verify the left inequality in (16). In view of (19) we have
![]()
From the particular case
of (16) we have that
![]()
Therefore, if in an exact problem
some three successive triangles do not contain nodes then the problem is not poised.
Also, in view of (17), we have that an exact problem is not poised if there are no nodes in the first or the last triangles of the strip.
In the last subsection we consider the case when there are no nodes in two successive triangles which do not include the first or the last triangles of the strip.
7.2. Reduction “0 + 0”
Theorem 7.2 Given an exact problem
where the strip consists of n triangles. Suppose that some two successive triangles
and
where
do not contain nodes. Then the problem
is poised if and only if the both fol- lowing two reduced problems
(20)
are exact and poised.
Proof. Let us assume that the both reduced problems in (20) are poised. Notice that then the problem
is exact. Now let us prove, by following Proposition 1.3, ii), that the problem
is poised, too. Thus, assume that
From here we get that
and
Since the two subproblems in (20) are poised, we conclude that s vanishes on the triangles
and
Therefore s vanishes also at the left side of the triangle
and at the right side of the triangle
In particular s vanishes at all the vertices of triangles
and
Thus it vanishes on these two triangles too. Hence ![]()
Next let us assume that the problem
is poised and prove that the both reduced problems in (20) are poised.
Let us show first that the both reduced problems in (13) are exact. There are
and
triangles in the reduced problems (20), respectively. Therefore for exact- ness we need
and
nodes, respectively, altogether
nodes. Now, assume by way of contradiction that a subproblem in (20) is not exact. Then a sub- problem is overdetermined and the other is underdetermined. Therefore, by Theorem 3.1, i), the problem is not poised, which is a contradiction.
Finally, let us show that both the reduced problems in (20) are poised. Assume by way of contradiction that one of them is not poised. Then again, by Theorem 3.1, i), the problem is not poised, which is a contradiction.