Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have an equidimensional $n$-dimensional simplicial complex $\Delta \subseteq \mathbb Q^n$; i.e., $\Delta$ is the union of finitely many $n$-simplices that intersect only along proper faces. (I really do mean to use the same $n$.) By an $n$-simplex, I mean the convex hull of $n+1$ affinely independent points in $\mathbb Q^n$. In this setup, a boundary facet is any $(n-1)$-simplex that is a facet of exactly one of the $n$-simplices that make up $\Delta$. Each boundary facet lies on a unique hyperplane, and the $n$-simplex to which it belongs lies entirely on one halfspace.

I'm having trouble proving the geometrically reasonable (maybe even obvious!) claim that the intersection of these halfspaces is contained in $\Delta$.

Question: Is it true that the intersection of these halfspaces is contained in $\Delta$? If so, can you point me to a reference? I couldn't find a proof of this in Ziegler's Lectures on Polytopes.

One thing that is throwing me off is that the claim isn't true if $\Delta$ isn't of full dimension. For instance, consider the situation in this picture: counterexample picture. Here the intersection of the boundary facets isn't even bounded.

I'm not a discrete mathematician, so thanks for bearing with me.

share|improve this question
    
For a complex $\Delta$ let $\mathcal{H}(\Delta)$ be the family of the halfspaces as defined in the question. Consider a halfspace $H\in \Delta$. Then $\{H'\cap H : H'\in\mathcal{H}(\Delta)\}$ contains $\mathcal{H}(\Delta\cap H)$. –  Boris Bukh Jul 24 '11 at 18:03
    
@Boris: can you expand on $H \in \Delta$? I don't quite get what you mean. –  Courtney Gibbons Jul 24 '11 at 19:41
    
Intersection of a boundary halfspace with the complex only reduces the set of halfspaces determined by the complex (of course, you might need to retriangulate any simplex that is intersected by hyperplane). Thus if we start taking the intersection of one halfspace at a time, we will end up with a subset of $\Delta$. –  Boris Bukh Jul 24 '11 at 20:35

1 Answer 1

up vote 3 down vote accepted

I'll risk a proof, assuming that by "the intersection of these halfspaces" you mean "the intersection of all the halfspaces of all the boundary facets."

Let point $x$ be in this intersection, and assume for the purposes of contradiction that $x$ is exterior to $\Delta$. Form an arrangement of hyperplanes $\cal{A}$ by all the hyperplanes determined by $x$ and all the ridges ($(n{-}2)$-dimensional facets, e.g., edges of tetrahedra) of $\Delta$. Find some point $z$ that is inside $\Delta$ but does not lie on $\cal A$. Such a $z$ exists because $\Delta$ cannot lie entirely within a hyperplane of $\cal{A}$. Now aim a ray $r$ from $x$ to $z$, and let $y$ be the first point on this ray that coincides with a point of $\Delta$. This $y$ must lie in the relative interior of some facet of some simplex $\sigma$ of $\Delta$, for if instead it lay on a ridge, then $y$, and therefore $z$, would lie on $\cal{A}$. The halfspace of this facet must be oriented so that it includes $\sigma$ and excludes $x$. So $x$ is afterall not inside the intersection of all the boundary halfspaces.

Of course it is possible that the intersection of the halfspaces is the empty set, but I assume you would treat that as contained in $\Delta$.

share|improve this answer
    
That is what I meant. Thanks! You've saved me many future headaches from trying to prove this with epsilon balls. :) –  Courtney Gibbons Jul 24 '11 at 19:39

Your Answer

 
discard

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.