# Find a point in a polytope that always cuts off a constant fraction of the polytope.

I have $k$ linear inequalities in $\mathbb{R}^n$, which we can express as $Ax \ge c$ (where $A \in \mathbb{R}^{k \times n}$ and $c \in \mathbb{R}^k$). Assume that the set of $x \in \mathbb{R}^n$ that satisfy this inequality is bounded.

I want a method of choosing a point $p$ in the polytope defined by these inequalities. I want the method to have the following property:

There exists a fraction $0 < f < \frac{1}{2}$ such that every hyperplane through $p$ divides the polytope into two figures, each of which contain at least $f$ of the total original area of the polytope.

The catch: $f$ cannot depend on $A$ or $c$. So I need a method that produces a point that always cuts the polytope into two regions, each of which contains (for example) at least 1/3 of the original area.

Is this possible?

• For posterity, I would like to add: the fraction cut by the centroid is $(\frac{n}{n+1})^n$. This converges to $\frac{1}{e}$ as $n$ goes to $\infty$, so for simplicity, you can just use $\frac{1}{e}$ as the value for $f$. – GMB Apr 17 '13 at 21:00
• This solved not only your problems. :-) More than ten years ago I found a simple but non-algorythmic proof based on Helly theorem for not necessarily convex case with the exact fraction cut bound $1/(n+1)$. And I was wondering about the convex case. Can you provide a link to the result on the fraction cut by the centroid? Thanks. – Alex Ravsky May 5 '13 at 19:39