.dcmath - UNDER CONSTRUCTION

CONVEX COMBINATIONS

One specific type of linear combination that often arises is a convex combination. A convex combination of vectors is formed when we require the coefficients of a linear combination to all be positive and sum to one, ie. A1x1+A2x2++Anxn,withixi=1,xi0 A_1 x_1 + A_2 x_2 + \cdots + A_n x_n, \qquad with \qquad \sum_i x_i = 1, \qquad x_i \geq 0 Note that we also write this constraint in more compact notation as 1Tx=1, x0 \mathbf{1}^Tx = 1, \ x \geq 0 or even more simply as xΔnx \in \Delta_n where Δn\Delta_n is the nnD simplex. Visually, a convex combination of vectors live in the space between the vectors or the convex hull. For any two vectors A1A_1 and A2A_2, A112+A212A_1 \tfrac{1}{2} + A_2 \tfrac{1}{2} is the vector halfway between the two vectors; for nn vectors iAi1n\sum_i A_i \tfrac{1}{n} is the center of the set of vectors ("average" vector of the set); etc. Different convex combinations of vectors {A1,A2,A3}R3\big\{A_1,A_2,A_3\big\} \in \mathbb{R}^3 are illustrated in the figures below.

1 / 5
Caption Text

We can also show convex combinations of two, three, four, and five vectors.

A convex combination between just two vectors is often written in the form y=A1(1α)+A2α y = A_1 (1-\alpha) + A_2\alpha with 0α10 \leq \alpha \leq 1 . We notice that if we start out with α=0\alpha = 0, y=A1y=A_1. We note that we can rearrange the above expression to show explicitly how yy changes with α\alpha y=A1+(A2A1)α y = A_1 + (A_2-A_1)\alpha As \alpha moves from 0 to 1, yy starts at A1A_1 and then adds back little bits of the difference from A1A_1 to A2A_2 until yy reaches A2A_2. This perspective is illustrated in the figure below.

1 / 5
Caption Text

Keeping α\alpha between 0 and 1 keeps yy on the segment between A1A_1 and A2A_2. If we relax this condition and allow α\alpha to be negative or greater than 1, we trace out a whole line that runs through A1A_1 and A2A_2. α<0\alpha<0 extends past A1A_1; α>1\alpha > 1 extends off past A2A_2. Note that here x1=(1α)x_1 = (1-\alpha) and x2=αx_2 = \alpha. Removing the restriction on α\alpha is equivalent to removing the restriction that x10x_1 \geq 0 and x20x_2 \geq 0. By construction, we still have x1+x2=(1α)+α=1x_1 + x_2 = (1-\alpha) + \alpha = 1

Note that this extension to the line through A1A_1 and A2A_2 applies to larger numbers of vectors as well. For example for three vectors {A1,A2,A3}\big\{A_1,A_2,A_3 \big\}, removing the restriction that x0x\geq 0 expands the convex set to the plane shown below. Note the signs of x1x_1,x2x_2, and x3x_3 in each part of the plane.

More Drawing: Is a Point Inside a Triangle? (Difficulty: 3/10)

The above construction can be quite useful for determining quickly if a point is inside a triangle, tetrahedron, or hyper-tetrahedron. (This has many applications. For example it is a critical step in the implementation of the quickhull algorithm for computing convex hulls of points.) We focus on the case of three points in 2D, ie. determining if a point is inside a triangle.

To determine if a point yR2y \in \mathbb{R}^2 is inside a triangle formed by points {A1,A2,A3}R2\big\{A_1,A_2,A_3\big\} \subset \mathbb{R}^2, we can form the following system of equations [y1]=[A1A2A31T]undefinedM[x1x2x3]=[A11A12A13A21A22A23111]undefinedM[x1x2x3] \begin{bmatrix} y \\ 1 \end{bmatrix} = \underbrace{ \begin{bmatrix} \begin{matrix} | & | & | \\ A_1 & A_2 & A_3 \\ | & | & | \\ \end{matrix} \\ \begin{matrix} - & \mathbf{1}^T & - \end{matrix} \end{bmatrix} }_{M} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \underbrace{ \begin{bmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ 1 & 1 & 1 \end{bmatrix} }_{M} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} The last row this system of equations requires xx to sum to 1, ie. xx generates linear combinations in the plane shown in the figure above. The first two rows then say that yy is a linear combination of the AiA_i vectors. Note assuming this system is invertible, we can compute x=M1yx=M^{-1}y. After computing xx one can immediately read off which section of the plane yy is in based on the signs of the elements of xx. If x0x\geq 0, then yy is in the triangle. For fast implementation a 3×33\times 3 matrix MM can be inverted explicitly (see inverse formulas).

Note: this system will always be invertible unless the triangle shown above collapse to a line and the problem is ill-posed. One could still actually take the pseudo-inverse which would determine if the projection of yy onto that line was inside the convex combination of the points. (I think.)

For tetrahedrons or hyper-tetrahedrons in nnD, this formula extends to checking if yRny \in \mathbb{R}^n is a convex combination of n+1n+1 points {A1,,An+1}\big\{A_1,\dots,A_{n+1}\big\}. The equation then becomes [y1]=[A1An+11T]undefinedM[x1xn+1] \begin{bmatrix} y \\ 1 \end{bmatrix} = \underbrace{ \begin{bmatrix} \begin{matrix} | & & | \\ A_1 & \cdots & A_{n+1}\\ | & & | \\ \end{matrix} \\ \begin{matrix} - & \mathbf{1}^T & - \end{matrix} \end{bmatrix} }_{M} \begin{bmatrix} x_1 \\ \vdots \\ x_{n+1} \end{bmatrix}

Taking x=M1yx = M^{-1}y, one can similarly check that x0x\geq 0.
More Math: Coordinate Transformations on Convex Hulls (Difficulty: 4/10)

When we're working with a convex hull of a set of points, we may often want to write different coordinate systems based on those points. We list several useful coordinate transformations below along with explicit representations of their inverses, diagrams, and intuitive explanations. Of course, other useful transformations are possible. We write the formulas for points in Rn\mathbb{R}^n, but we draw figures for points in R3\mathbb{R}^3 and R4\mathbb{R}^4. The convex hull for 3 points in R3\mathbb{R}^3 is a triangle; for 4 points in R4\mathbb{R}^4 the convex hull is a 3D tetrahedron which can visualized. The first n1n-1 coordinates in our tranformations will line up explicitly with each convex hull. The last coordinate will be related to the vector 1\mathbf{1}.