Geometric Algebra

Geometric Algebra > Designing Geometric Algebras - Interpolating Points

Designing Geometric Algebras - Interpolating Points

Now for an application that makes use of the fact that we can represent arbitrary shapes as GA objects. Let's start with a concrete example. We have three points which are also shown in the figure below. We want to find

y

values for other values of

x

between our three points. This is called interpolation for

x

between our known points, and extrapolation for

x

outside of our known points. In other words, we want to find a curve that reasonably interpolates our points.

\begin{matrix} (1) & \begin{aligned} (x_{1}, y_{1}) & = (- 3, 2) \\ (x_{2}, y_{2}) & = (0, 3) \\ (x_{3}, y_{3}) & = (1, 1) \end{aligned} \end{matrix}

_{Figure 1 - Blue: Points we want to interpolate.}

A natural choice for a family of curves are polynomials in

x

, so we will focus on them for now but the procedure outlined in this article will work for any other family of curves too. It turns out that

N

points unique determine the coefficients of a degree

N - 1

polynomial. For our example,

y = c_{0} + c_{1} x + c_{2} x^{2}

is of degree two so its coefficients can be found given three points. The solution we want to find is shown below.

_{Figure 2 - Blue: Points we want to interpolate. Green: Second degree polynomial interpolating the points.}

Representing polynomials in Geometric Algebra

In the first section we learnt that we can represent polynomials in Geometric Algebra by introducing a basis vector for each term of it, including the

y

term. For our concrete example we would have four basis vectors corresponding to

1, x, x^{2}, y

and the up function which maps

(x, y)

points to vectors in the 4D space is

\begin{matrix} (2) & u p (x, y) = 1 e_{0} + x e_{1} + x^{2} e_{2} + y e_{3} \end{matrix}

Finding the interpolating object

Now we can represent points. How do we get an object representing a curve that goes through all points? We know we can join points together to make shapes which go through all of them with the wedge product. In general we have the following equation which results in the pseudovector

p

\begin{matrix} (3) & p = ⋀_{n = 1}^{N} u p (x_{n}, y_{n}) = \sum_{n = 0}^{N - 1} p_{n} e_{n}^{*} \end{matrix}

Where

N

is the number of points. This should give us some object representing a shape that goes through all of the points that were joined.

Getting the interpolating polynomial coefficients from the object

We can examine this object by applying the Outer Product Null Space / Join Null Space equation:

\begin{matrix} (4) & \begin{aligned} p \land u p (x, y) & = (p_{0} e_{0}^{*} + p_{1} e_{1}^{*} + p_{2} e_{2}^{*} + p_{3} e_{3}^{*}) \land (1 e_{0} + x e_{1} + x^{2} e_{2} + y e_{3}) = \\ = e_{0123} (p_{0} + p_{1} x + p_{2} x^{2} + p_{3} y) = 0 \end{aligned} \end{matrix}

To bring it into the usual form we still need to bring

y

on the other side with a coefficient of

1

. We can also get rid of the pseudoscalar

e_{1234}

. This results in

\begin{matrix} (5) & y = - \frac{p_{0}}{p_{3}} - \frac{p_{1}}{p_{3}} x - \frac{p_{2}}{p_{3}} x^{2} \end{matrix}

So indeed our object represents a polynomial. In general, to get the ordinary coefficients

c_{n}

from

p

we have

\begin{matrix} (6) & c_{n} = - \frac{p_{n}}{p_{N}} \end{matrix}

We can see that the coefficients of the polynomial can be directly read off of

p

's coefficients. This is all that we needed. We wedged together some points into a pseudovector, we know that the object goes through all of our points, and from the pseudovector's coefficients we can easily get the interpolating polynomial's coefficients.

For our concrete example we have the following pseudovector for representing the polynomial

\begin{matrix} (7) & p = u p (- 3, 2) \land u p (0, 3) \land u p (1, 1) = 36 e_{0}^{*} - 17 e_{1}^{*} - 7 e_{2}^{*} - 12 e_{3}^{*} \end{matrix}

Reading off the coefficients and dividing by

y

's coefficient yields the interpolating polynomial equation

\begin{matrix} (8) & y = - \frac{36}{- 12} - \frac{- 17}{- 12} x - \frac{- 7}{- 12} x^{2} = 3 - \frac{17}{12} x - \frac{7}{12} x^{2} \end{matrix}

which corresponds exactly to the green curve in the figure 2.

Algorithm Summary

To summarize the procedure, given N points

(x_{n}, y_{n})

We want to interpolate with a polynomial of degree $N - 1$ with coefficients $c_{n}$ : $y = \sum_{n = 0}^{N - 1} c_{n} x^{n}$
Use GA with N basis vectors and up function: $u p (x, y) = y e_{N} + \sum_{n = 0}^{N - 1} x^{n} e_{n}$
Build polynomial object $p$ by wedging together N up projected points: $p = ⋀_{n = 1}^{N} u p (x_{n}, y_{n})$
Extract interpolating polynomial coefficients $c_{n}$ from $p$ : $c_{n} = - \frac{p_{n}}{p_{N}}$

Conclusion

We started by looking at what interpolation is and we chose to use polynomials for interpolation. We then applied our knowledge from the previous section to represent polynomials in Geometric Algebra. With the wedge product we constructed an object representing the interpolating polynomial from which we could just read off the coefficients.

This process generalizes to any number of points and it uses only very simple GA operations, so it might be preferable over the usual methods like using matrices or Lagrange polynomials. While we were focusing on polynomials here, this process works identically with other functions too, as no assumptions about the basis functions were made. The only change is to use a different up function.

Next: Design of Geometric Algebras - Tangent Objects