2
$\begingroup$

We are given a $d$-dimensional convex polytope ${\cal P}$ in $N$-dimensional space where $d<N-1$. Consider several planes $P_i$ corresponding to inequalities $f_i(X)\ge 0$. We are given that each such plane intersects ${\cal P}$ such that there are points in ${\cal P}$ that violate the corresponding inequality and others that satisfy it. Let these intersections create $k$ regions $R_1,\ldots,R_k$ in polytope ${\cal P}$ such that $\cup_iR_i={\cal P}$ and each $R_i$ corresponds to the violated side of some inequality. Also, there must exist at least one point in each $R_i$ such that there is a unique $P_i$ whose inequality is violated by that point. We would like to get a non-trivial upper bound on the value of $k$. Any suggestions, ideas on how to arrive at such a bound would be highly appreciated.

$\endgroup$
  • $\begingroup$ What is the "trivial" upper bound? Infinity? $\endgroup$ – Yoav Kallus May 26 '15 at 15:01
  • 2
    $\begingroup$ Consider the configuration of spherical caps on a 2-sphere: each of $k$ caps is a hemisphere, with centers tracing a line of latitude near the north pole; each cap dips down at its southernmost point to a latitude $-\epsilon$, and each cap intersects the next one to the east at a latitude $-\delta$; and add one more cap consisting of all points of latitude no more than $-\delta$. Each cap includes a point not covered by any other cap, and $k$ can be as large as you wish. Since you want a polytope, you can triangulate the ball, and if you do it finely enough, you will preserve these properties. $\endgroup$ – Yoav Kallus May 26 '15 at 15:33
2
$\begingroup$

An attempt to illustrate Yoav's construction:


            Hemispheres
(I'm responsible for any misinterpretations.)

$\endgroup$

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.