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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is the "trivial" upper bound? Infinity? $\endgroup$– Yoav KallusCommented May 26, 2015 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 KallusCommented May 26, 2015 at 15:33
Add a comment
|
1 Answer
$\begingroup$
(I'm responsible for any misinterpretations.)
$\endgroup$
0
An attempt to illustrate Yoav's construction:
(I'm responsible for any misinterpretations.)
answered May 26, 2015 at 23:21