# Higher dimensional convex hull

Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=$ { $x \in Vert(S)$ | $xv$ is an edge of $CH(S)$ }.

My question is best stated using an example in 2-D:

In this example, $S =${ $v_1, v_2, v_3, v_4, v_5$} and $v_1, v_2, v_3, v_4, v_5$ in clockwise order constitutes $Vert(S)$. There exists a line $L$ between $v_1$ and $CH(S -${ $v_1$}$)$. If we link $v_1$ with every other 4 points, we will obtain 4 new points $p_2, p_3, p_4, p_5$ on $L$, where $p_i$ is the intersection of $L$ and the line $v_1v_i$. You will find that { $p_2, p_5$ } $= Vert($ { $p_2, p_3, p_4, p_5$ } $)$.

Here comes my problem. Given a finite set $S$ in higher dimensional (i.e. >= 3) vector space, we can find $Vert(S) =$ { $v_1, v_2, \cdots, v_h$ }. Now consider a point $v \in Vert(S)$. There exists a hyperplane between $v$ and $CH(S -${$v$}$)$. If we link $v$ with every other points in $Vert(S)$, we will get a set $P$ containing $h - 1$ points on the hyperplane.

Will the points in $P$ corresponding to $E(v)$ constitute $Vert(P)$? Or is there some related theorems?

-
For your first paragraph, specify that $S$ is a finite set. Then vertex and edge make sense. –  Gerald Edgar May 13 '13 at 16:59

I think the answer is yes. First observe that $CH(P) \subset CH(S)\cap H$: if $x\in CH(P)$ then $x$ is written as a convex combination of things which are convex combinations of vertices of $CH(S)$, so is a convex combination of vertices of $CH(S)$.

Then we note that $CH(S)\cap H$ has as its vertices the points in $P$ corresponding to $E(v)$ (in general this is going to be all of $E(v)$ are, which are all contained in $P$ of course so $CH(S)\cap H \subset CH(P)$ and the two sets are equal, and we know the vertices of $CH(S)\cap H$

To see that $CH(S) \cap H$ has the correct vertices, the faces of $CH(S) \cap H$ correspond to faces of $CH(S)$ with their dimension dropped by at most 1 (if the face happens to be parallel to the hyperplane, then it will not drop in dimension). The edges in $E(v)$ cannot be parallel to the hyperplane because that means the hyperplane does not separate $v$ and the corresponding vertex on the other side of the edge

-
I'm just a beginner. Could you explain the second and the third paragraphs more clearly? Or what theorems that is your statement based on? –  echo May 13 '13 at 17:40
If you think of CH(S) as being a polyhedron: A polyhedron P of dimension n has a face F of dimension d if there are n-d linearly independent inequalities for P which are active (have an equality at that point). So if we take P=CH(S), the edges are the places were n-1 inequalities are active. If we restrict to $CH(S)\cap H$, inequalities for $P$ correspond to inequalities for $CH(S)\cap H$ inside of $H$. The edge which originally had n-1 active inequalities still has n-1 active inequalities inside of $H$ as long as $H\cap edge$ is not equal to the whole edge –  David Benson-Putnins May 13 '13 at 17:51

The operation that you are describing is known as the "vertex figure". I suggest that you have a look at Günter Ziegler's book "Lectures on Polytopes". This is well explained at Chapter 2. I guess that the particular statement that you are looking for is Proposition 2.4 that states a bijection between (k-1)-faces of the vertex figure at v with k-faces of the original polytope that contain v.

-