1
$\begingroup$

This is just for the convex hull of finitely many points in Euclidean space, without a choice of coordinates. The axiomatization of Euclidean geometry I have in mind is Tarski's axioms, for which betweenness is a primitive notion.

  • Define the convex $0$-skeleton to be the finite set of points we are starting with.
  • Define the convex 1-skeleton to be the set of all points which are between any two points of the convex 0-skeleton.
  • Define the convex 2-skeleton to be the set of all points which are between any two points of the convex 1-skeleton.
  • ...
  • Define the convex $n$-skeleton to be the set of all points which are between any two points of the convex $(n-1)$-skeleton.
  • ...

Then it follows (I believe) from the upper dimension axiom that these sets have to stabilize for some $n$ (i.e. the convex $m$-skeleton equals the convex $n$-skeleton for all $m \ge n$ for some $n$).

Question: Then is the convex hull is just the convex $n$-skeleton for the smallest $n$ for which the convex $m$-skeletons equal the convex $n$-skeleton for all $m \ge n$?

Is there any better coordinate-free definition which doesn't rely upon induction?

A pointer to a reference would be appreciated.

Attempt: Using coordinates, we just have that, given finitely (an integer $p$) many points , their convex hull is the set of all points which are a convex combination of the $p$ points.

Using the coordinate realization/model of Tarski's axioms, betweenness is equivalent to being a convex combination of 2 points (i.e. the point $b$ is between the points $a$ and $c$ if and only if $b$ is a convex combination of $a$ and $c$).

So trying to verify whether this inductive definition is correct comes down to verifying that any convex combination of $p$ points can be constructed inductively from convex combinations of two points at a time. I am pretty certain this follows from distributivity and associativity.

(Not that certain though or else I wouldn't be asking this question.)

$\endgroup$
5
  • 1
    $\begingroup$ Are you asking whether this is a correct definition of the convex hull in $\mathbf{R}^n$? Or is there a logic component to the question? $\endgroup$
    – user49640
    May 3, 2017 at 6:55
  • 1
    $\begingroup$ Other inductive definition is "the convex hull of $p+1$ points is the set of points between any point of the convex hull of the $p$ first points and the last point; the convex hull of a singleton is this point". $\endgroup$
    – user65203
    May 3, 2017 at 7:28
  • 1
    $\begingroup$ I guess that it is harmless to generalize the definition of betweenness to more than two points. Then the convex hull is the set of points between the points of the "$0$-skeleton". $\endgroup$
    – user65203
    May 3, 2017 at 7:30
  • $\begingroup$ @user49640 the former -- I haven't thought about this enough to make it a question about mathematical logic $\endgroup$ May 3, 2017 at 9:05
  • 1
    $\begingroup$ @YvesDaoust How does does one generalize the definition of betweenness to more than two points? I think this is what I am trying to understand. $\endgroup$ May 3, 2017 at 9:06

1 Answer 1

1
$\begingroup$

This is true, even for infinite sets, as a consequence of Carathéodory's theorem.

Namely, if the dimension of the space is $n$, and $x$ is a point in the convex hull of your set $S$ (finite or not), then you can select points $p_1, p_2, \dots, p_{s} \in S$, $s \leq n + 1$, and constants $a_1, a_2, \dots, a_{s} > 0$, such that $$x = a_1 p_1 + \dots + a_s p_s, \quad a_1 + \dots + a_s = 1.$$

Then you can prove that $\frac{a_1}{a_1 + a_2} p_1 + \frac{a_2}{a_1 + a_2} p_2$ is in your $1$-skeleton (since it is between $p_1$ and $p_2$), that $\frac{a_1}{a_1 + a_2 + a_3} p_1 + \frac{a_2}{a_1 + a_2 + a_3} p_2 + \frac{a_3}{a_1 + a_2 + a_3} p_3$ is in your $2$-skeleton (since it is between $p_3$ and the last point), and so on by induction.

However, you can do better than this. By grouping the $p_i$'s first in twos, then in fours, in eights, etc., you can show that the whole convex hull is in your $k$-skeleton as soon as $2^k \geq n + 1$. So calling it a "$k$-skeleton" is misleading, as its dimension will typically be $2^k - 1$. (For example, the set of points between two opposite edges of a tetrahedron is the tetrahedron.) If you want to have a $k$-dimensional object at each stage, it might be preferable to only add points that are between a point in the $(k-1)$-skeleton and a point that is actually in $S$. The argument using Carathéodory's theorem shows that this works.

If you don't use Caratheodory's theorem, it's only clear that the second construction will terminate after $|S|$ steps, rather than $n + 1$.

$\endgroup$

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.