Splines and Bezier Curves: Part I

I need splines for envelopes and other thrill parades.

Consider the construction of a simple (Bézier) curve:
(It's interactive.  Press the button. Drag points around.  Press play.)
This is a Java Applet created using GeoGebra from www.geogebra.org - it looks like you don't have Java installed, please go to www.java.com
At each step, the number of points decreases by one.  Continue until there is one point left.  The locus of this point is a curve.  Each sliding point gets its coordinates from two points above it.  If the curve is traced by point S, for example, it can be written
          S = StartingPoint + (End−Start)t
          S = R_0, + (R₁ − R₀)t
We add and multiply the components indpenendently:
         S = (x_r0+ [x_r1−x_r0]t,   y_r0+ [y_r1−y_r0]t)
...and t is the percent of the distance S has traveled from start to finish.  If R₁ and R₂ are moving, S depends on that motion as well:
        S   = R₀ + (R₁−R₀)t,   where
        R₀ = Q₀ + (Q₁−Q₀)t
        Q₀ = P₀ + (P₁−P₀)t,    etc.

This is easy to write, but we must compute the P's before the Q's before the R's, before the S's.  To eliminate this dependency, we can write coordinates of the curve directly from the coordinates of the control points.  The result is a polynomial expansion.  I'm looking for a way to simplify this expansion, and therefore the calculation of the resulting curve.

Given  k+1  points
          
what can we say about the resulting curve, following the method illustrated above?  The procedure is the same for both x and y, so I will  consider only the x-values, and apply the result to the y-coordinates at the end.  So, I'm interested in the k+1 x-values,   .
Call First Order points, the k points that slide between these x-values, and label them A_i.
The First Order points sare thus  A₀, A₁,  . . . ,  A_k−1
The Second Order points:   B₀, B₁, . . . ,   B_k−2
The ith Order points: I₀, I₁, . . . ,  I_k-i
       . . .
The(k−1)st Order is the two points M₀, M₁
The last point is  N.

Order 1:
Two ways of writing A₀ seem promising:
     
And then,


Now expand B₀ into a polynomial in t, x₀, x₁, and x₂.
Using (1):

A rule I've made up is that if I have two simultaneous polynomials going on, there is a way to sort that shit out.
Using (2):

I will use (2).

REPEAT

Hello there, binomial expansion.

(Hello, Ryan)
■

STOP
I have three successive expansions, whose coefficients agree term-for-term with the coefficients of the binomial expansion (x+1)^k. I now need to prove that
   If a given step in the expansion is in the form of the binomial expansion, then the next step is in that same form. 

Suppose I have the (k−1)st order.  Call the point M₀. That is, I have


Now, iterate in the same way as above




Alternately, you can just hit yourself in the face with a bat.  Collecting like terms...


And simplifying coefficients,

At last!
     

Which is to say,
     
Where the C_r are the coefficients of the expansion of  (x+1)^k.

Being the thing to be proved.

■

N is the only point left.  The locus of N is the equation of the curve.  Copying the formula to the y-coordinate, we have, for a kth order spline from k+1 initial points   ,
a polynomial of order k, with parametric equation:


The coefficients C_r are the same for every curve of the same order, and the polynomial is in powers of t.   Given the order of the curve, we can precompute the C_r, and use them for every curve of that order.  We can also precompute the t^r(1−t)^r for evenly spaced values of t.  A fixed amount of memory is required to turn (a) into:

This is the dot product of two vectors.  The values of the first vector vary with t but can be precomputed.  The second vector is the list of control points.  All terms and independent: the multiplications can be done in parallel with the summation.

There remain some difficulties.  As k increases,  t^r(1−t)^r   spends less of the interval 0...1 in useful values-not-zero; much of the computation time might be wasted.  I could ignore the influence of most points, most of the time, but this does not seem promising if I want flexible, higher-order splines.   I also need to write  t^r(1−t)^r in a way that does not spend a lot of time with division near zero.
However, since the powers and factorials are known in advance,  we can redistribute the computation however we wish, independent of the control points.

Although it appears complicated, the above procedure is simple compared to the task of constructing Newton's formulas.  Splines generalize ideally because we are making them up. The properties are not about the behavior of numbers; they are a result of our assumptions.  I might have, for example, begun with the assumption that I would build whatever curve is given by dot-product of (the coordinates of the points) with (the binomial expansion). The curve terminates in two points: we are constrained to working backward through the points in (1−t) at the same time that we move forward in t.  I did not see this.  I started with a method which I know gives a polynomial curve of any order, and then generalized it.  Generalization is  called storytelling.  If it happens to also be meaningful, that meaning is a value judgment outside of mathematics.  It is meaningful to us.  Or it is descriptive of some phenomenon.  Hunting for the meaning of relationships we have made up inside the invented structure is [dumb].  In the present example, the situation is simple:

Using Newton's method, IF my polynomial approximation is also the unknown function F(x,y) THEN I am going in a logical circle: I can make up whatever I want.  I have successfully abstracted: I am left with a purely formal method for building arbitrary polynomials (a container).  Rad.  But my assumption and conclusion are the same.  I will accept whatever curve results, as long as it is smooth and makes sense to me in some way (for example, if I build handles to control it).  I have abandoned the entire difficulty of the problems Newton developed this method to solve:

 Suppose we are given a differential relationship and we cannot  just make up any answer we wish.  We must find a unique approximation of the solution(s) to a physical phenomenon which does not obey us, and for which a number of initial conditions are known.

Absent this constraint, I can draw ponies with the polynomials.  I don't even have to fit them to points.  The only meaningful question is what I intend to do with them.  I made this page up.  The rest in Newton.  The date is 1687, and he has just published the Principia.

It is shameful that contemporary mathematics is often grounded in the assumption that there are mysterious, deep formal rules which must be discovered, without which we cannot obtain general solutions to problems which pose no structural difficulty.  The error is informal. If we are intent upon generalization and abstraction, the solution is to make something up.
Q.E.D.

■