MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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