We are given a $d$dimensional convex polytope ${\cal P}$ in $N$dimensional space where $d<N1$. 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 nontrivial upper bound on the value of $k$. Any suggestions, ideas on how to arrive at such a bound would be highly appreciated.
2

$\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 2sphere: 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$
(I'm responsible for any misinterpretations.)
$\endgroup$
An attempt to illustrate Yoav's construction:
(I'm responsible for any misinterpretations.)