More on linear interpolation

Gerald Farin Computer Science and Engineering Arizona State University Tempe, AZ 85287-5406

                    email farin@asu.edu

February 27, 2001

1 Vector arguments

Since linear interpolation is an affine map, we have the following:

l((1 − s)c + sd) = (1 − s)l(c) + sl(d).  (1)

This simply states that a relationship of points in the domain is left unchanged for the corresponding points i the range.

We may take this one step further: if a vector is defined in the domain, then that definition also carries over to the range. If c and d are two points on the real line, the domain, they define a vector α by setting α = d − c. The corresponding vector in the range is then defined as

l(α) = l(d) − l(c).  (2)

2 Vectors and blossoms

Menelaos’ theorem is an assertion about the commmutativity of supplying two different (point) arguments to piecewise linear interpolation of a polygon consisting of three points. Instead of using two points in the real line as arguments, we may use a point and a vector. If t the point and α is the vector in the real line, our generalized Menelaos’ theorem states

l(t, α) = l(α, t).  (3)

It is easy to check that both expressions equal (t − 1)p_{1} + (1 − 2t)p_{2} + tp_{3}.

3 Derivatives and blossoms: affine

First, an identity, closely resembling Leibniz’ formula for derivatives. Let t be a point on the real line and let α be a vector in the associated 1D linear space. Then

b[(t + α)^{<n>}] = ∑_{i=0}^{n} \binom{n}{i}b[t^{<n−i>}, α^{<i>}].  (4)

This is easily proved (check for n = 2!).

The derivative of a curve x(t) with respect to a 1D vector α is defined as

D_{α}x(t) = lim_{h→0} \frac{1}{h}[x(t + hα) − x(t)].

Since we are dealing with curves which are defined via blossoms, we get

D_{α}b[t^{<n>}] = lim_{h→0} \frac{1}{h}[b[(t + hα)^{<n>}] − b[t^{<n>}]].

Invoking (4), we have

D_{α}b[t^{<n>}] = lim_{h→0} [ ∑_{i=0}^{n} \binom{n}{i}b[t^{<n−i>}, (hα)^{<i>}] − b[t^{<n>}]].  (5)

Thus

D_{α}b[t^{<n>}] = lim_{h→0} [ ∑_{i=0}^{n} \binom{n}{i}h^{i}b[t^{<n−i>}, α^{<i>}] − b[t^{<n>}]].  (6)

Upon taking the limit and observing all terms containing h powers of order two and higher will vanish, we have

D_{α}b[t^{<n>}] = nb[t^{<n−1>}, α].  (7)

In most cases, one would choose α to have length one; then the blossom steps with respect to α are simply difference steps. and the D_{α} will become the familiar \frac{d}{dt}.

4 Derivatives and blossoms: projective

The above reasoning has to change if we study derivatives in projective space. Since there are no vectors, we replace the vecotr α by a point s. Following the same reasoning as above, we obtain

D_{s}\underline{b}[t^{<n>}] = n\underline{b}[t^{<n−1>}, s].  (8)

Note that the derivative changes as a function of s!