3
$\begingroup$

I am new to convex hulls and I have encountered the following statement:

Given a set of n points in a vector space $\{x_1 ... x_n \}$, every point $x_0$ in the convex hull they form is obtained from the expression:

$$ x_0 = \sum_{i=1}^n \alpha_i x_i$$ where $\alpha_i\geq0$ and $\sum_{i=1}^n\alpha_i=1$, with different coefficients $\alpha_i$ giving different points, always within the convex hull.

I have seen in this other answer a very clear example in $\mathbb R^2$ with only three points, for which the convex hull is just the convex combination of those three points, and corresponds to the points within the triangle formed by them. In $\mathbb R^2$, but for $n$ points, the convex hull is just the set of all points inside the polygon formed by the "outer" points of the set - enclosing the rest of "inner" points. (Formally, the smallest convex set which contains all the points in our set of $n$ points.)

If we added another point inside the triangle, the convex hull would remain the same; however, based on the expression I provide, that new point should also be included in the weighed sum (the sum goes from $0$ to $n$), in spite of lying inside such polygon and therefore not altering the convex hull. Why would such inner points be included in the sums? Are perhaps their coefficients zero (i.e. $\alpha_i=0$ precisely for those "inner" points)?

Additionally, if possible, I would like to know how the expression I give for the most general case is obtained, or at least how I could intuitively think about it to make it a bit more transparent.

$\endgroup$
3
$\begingroup$

When you include points in the interior of the convex hull in the defining set then the representation will not be unique. Different sets of coefficients can represent the same point. In fact an interior point in the defining set can be represented with its coefficient $1$ and the others $0$, and also represented as a convex combination of the vertices of the convex hull.

This is analogous to the definition of the span of a set in a vector space. The representation of points in the span will be unique if and only if the set is independent.

$\endgroup$
  • $\begingroup$ Thank you for the reply, this answers my main question. I think maybe the intuitive meaning is just to make up the position vector out of a certain percentage of each of the vectors of the set (up to its entirety 100%, or mathematically the sum of weights equal to 1), and therefore the final result being inside the hull. I wondered if there are more rigorous and formal ways to come up with the analytical expression - I didn't manage to find anything around in the web; even Wikipedia apparently only states it without deriving it from anywhere. $\endgroup$ – abcd Nov 25 '19 at 18:13
  • 1
    $\begingroup$ The definition as a weighted sum is perfectly rigorous and seems to satisfy your intuition. You can also define the convex hull as the intersection of all the half spaces that contain the given points. Then you can prove that the two definitions are equivalent. $\endgroup$ – Ethan Bolker Nov 25 '19 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.