Geometric Algebra: The Meet Operation

Background

The Meet operation in Geometric Algebra (GA) calculates the intersection of two subspaces. In set theoretical terms, the intersection is given by the relationship $M = A\cap{}B$ where M is the intersection (or Meet). Frequently in GA papers and books, you’ll find the elegant looking equation $M = A\cap{}B = (B^{*}\wedge{}A^{*})^{*}$ where $A^{*}$ indicates the dual of A. Unfortunately, calculating Meet is not so simple.

Related to the intersection of two subspaces, we can define a second quantity that is the difference between their union and intersection, which is called the symmetric difference or delta product.  Using this product, the intersection can be rewritten as $A\cap{}B = \frac{A + B – A\Delta{}B}{2}$.  In Geometric Algebra, the delta product of blades is defined as the highest grade part of the geometric product of A and B $A\cap{}B = \langle{AB}\rangle{}_{max}$.  The grade operation in the delta product stems from the way the geometric product automatically eliminates dependent factors.  Furthermore, the grade of the Meet can equally be formulated in terms of the delta product as $grade(A\cap{}B) = \frac{grade(A) + grade(B) – grade(A\Delta{}B)}{2}$.

The Algorithm*

Approach

Through the delta product, we now have a proper way of expressing how the two subspaces A and B relate to each other and can formulate an algorithm to compute it.  In the diagrams above, notice that the delta product includes both A and B but not their intersection while the dual of the delta product includes both the surrounding space as well as the intersection.  We can take advantage of this fact by computing the meet by projecting the dual of the delta product into the subspace A since whatever projects into A from the dual delta product is the intersection because the intersection is by definition a subspace of A.

Since the grade of the meet is not necessarily equal to the grade of $(A\cap{}B)^{*}$, we must first factor it into an orthogonal basis before projecting it into A.  Factoring a blade essentially involves probing the blade with a candidate basis vector and iteratively taking the basis vectors out of the blade until only one is left.  In order to start the process, a good candidate basis vector must first be selected.  Since the specific factorization doesn’t matter, we can simply select the element of the blade with the largest magnitude and go from there.  Since we are dealing with a blade in this case, we can simply project the vectors of the element chosen into the blade and iteratively remove those projections.  The algorithm looks like this given a blade B of grade k:

1. Calculate the norm of B $s = \Vert{}B\Vert{}$
2. Find the basis element E in B with the largest coordinate
3. Determine the vectors $e_{i}$ of E
4. Normalize B $B_{c} = B/s$
5. For each $e_{i}$ except for 1
• Project $e_{i}$ onto $B_{c}$ : $f_{i} = (e_{i}\rfloor{}B_{c})B_{c}^{-1}$
• Normalize $f_{i}$
• Remove $f_{i}$ from $B_{c}$ : $B_{c} \leftarrow{} f_{i}^{-1}\rfloor{}B_{c}$
6. The last $f_{i}$ factor is set to $B_{c}$ : $f_{k} = B_{c}$ and normalized.

The Basic Meet Algorithm

The meet can be taken between two blades A and B of different grades and here we’ll assume blade A is of equal or greater grade than blade B.  Given blades A and B:

1. Compute the dual delta product $S = (A\Delta{}B)^{*}$
2. Apply the factoring algorithm to S to get the factors $s_{i}$
3. Compute the grade of the meet $grade(A\cap{}B) = \frac{grade(A) + grade(B) – grade(A\Delta{}B)}{2}$
4. Set the meet result M to 1: $M = 1$
5. For each $s_{i}$
• Project $s_{i}$ into A: $p_{i} = (s_{i}\rfloor{}A)\rfloor{}A^{-1}$
• If the projection $p_{i}$ is not zero, accumulate it into M: $M \leftarrow{} M\wedge{}p_{i}$
• If $grade(M)$ is equal to that computed in step 3, break the loop

Circle Intersection

A simple example of the meet operation in use is the case of circle intersections.  If we define two circles.  If we take two circles C1 and C2 at (1, 0, 0) and (-1, 0, 0) respectively, each with a radius of 2, the meet operation will return a point pair.  In other words, the meet gives back a single object describing the two intersection points of the circle.

• $C1 = oe_1e_2 – oe_2\infty + 1.5*e_1e_2\infty$
• $C2 = oe_1e_2 + oe2\infty + 1.5*e_1e_2\infty$
• $S = C1\Delta{}C2 = -2*oe_1 – 3*e_1\infty$
• $S^* = -2*oe_2e_3 – 3*e_2e_3\infty$
• $s_1 = e_2, s_2 = e_3, s_3 = – \frac{2}{\sqrt{12}}o – \frac{3}{\sqrt{12}}\infty$
• $A\cap{}B = \frac{2}{\sqrt{12}}oe_2 – \frac{3}{\sqrt{12}}e_2\infty$

The result of the meet as calculated above is a point pair.  The points can be extracted by a simple equation that extracts the point pair’s axis and then pushes out a distance along this axis from their center point.  The equation is given by:

$P = p_{-}\wedge{}p_{+}$ where P is the point pair and

$p_{\pm} = \frac{P\mp\sqrt{P^2}}{-\infty\rfloor{}P}$ are the points.

For the case above, the points are located at $p_{\pm} = o \mp \sqrt{3}e_2 + 1.5*\infty$.

* see Geometric Algebra for Computer Science by Dorst et al, p. 536

This entry was posted in Computational Technique, Space and Geometry and tagged , , . Bookmark the permalink.

2 Responses to Geometric Algebra: The Meet Operation

1. Pingback: Alexander7

2. Pingback: jordan