1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
0
$\begingroup$

Actually, it seems I've committed a basic research fail and overlooked the centroid, which seems to solve all my problems.

Sorry for the quick question-and-self-answer.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – GMB Apr 17 '13 at 21:00
  • $\begingroup$ 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. $\endgroup$ – Alex Ravsky May 5 '13 at 19:39
  • $\begingroup$ @AlexRavsky glad to hear it! Here is my source - check equation 8.53 on page 293. Unfortunately, the "proof is too complicated to be given here," but maybe it's in the references somewhere - I haven't checked. $\endgroup$ – GMB May 7 '13 at 22:12

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.