Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T13:28:11Z http://mathoverflow.net/feeds/question/75413 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75413/angle-btween-coordinate-vector-and-normal-vector-of-facet-in-a-convex-polytope-a Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample han 2011-09-14T15:28:28Z 2011-09-15T04:01:02Z <h2>Definitions</h2> <p>Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets $F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as $\mathbf{w}_k=(w_{k1},\ldots,w_{kD})$. </p> <p>In the sequel, I will use $k$ as the index of $K$ facets and $d$ as the index of $D$ dimensions. Namely, $d\in \{1,\ldots,D\}$ and $k\in \{1,\ldots,K\}$.</p> <p>Let $\mathbf{p}=(p_{1},\ldots,p_{D})$ be a point in $\mathbb{R}^{D}$. Define</p> <p>$L_{d}=\{\mathbf{p}+\theta\mathbf{u}_{d}|\theta\in \mathbb{R}\},$</p> <p>where $\mathbf{u}_{d}$ is the vector of the form $(0,\ldots,0,1,0,\ldots,0)$ with a $1$ only at the $d^{\mathrm{th}}$ dimension.</p> <p>For $k=1,\ldots, K$, define</p> <p>$G_{k}=\{d|L_{d}\cap F_{k}\neq \emptyset\}.$</p> <p>Define $f:\mathbb{R}^{D}\times\mathbb{R}^{D}\rightarrow [0,1]$ as</p> <p>$f(\mathbf{x},\mathbf{y})=\frac{|\mathbf{x}^\mathrm{T}\mathbf{y}|}{\left\|\mathbf{x}\right\|\left\|\mathbf{y}\right\|}.$</p> <h2>My conjecture</h2> <p>For any $\mathbf{p}\in \mathrm{int}\mathcal{C}$, there exist $d$ and $k$ such that $d\in G_{k}$ and $f(\mathbf{u}_{d},\mathbf{w}_{k})=\max \{f(\mathbf{u}_{1},\mathbf{w}_{k}),\ldots,f(\mathbf{u}_{D},\mathbf{w}_{k})\}$.</p> <p>Can anyone provide a counterexample?</p> <h3>An illustrative example in $\mathbb{R}^2$</h3> <p>In particular, if we restrict ourself in $\mathbb{R}^2$, the above conjecture can be restated as follows:</p> <p>Let $p$ be a point in the interior of a convex polygon $\mathcal{C}$. Let $L_x$ and $L_y$ be two lines through $p$, which are parallel to $x$-axis and $y$-axis respectively. Consider all acute angles at intersections of $L_x$ $L_y$ and $\partial \mathcal{C}$, there is at least one angle $\geq$45°.</p> <p>The figure below gives an example.</p> <p><img src="http://home.in.tum.de/~xiaoh/q1p1.png" alt="alt text"></p> <p>I haven't found any counterexample in $\mathbb{R}^2$, and that's why I'm considering to generalise this conjecture into high dimensional space.</p> <p>Finally, any problem reformulation is also welcome.</p> http://mathoverflow.net/questions/75413/angle-btween-coordinate-vector-and-normal-vector-of-facet-in-a-convex-polytope-a/75432#75432 Answer by Ilya Bogdanov for Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample Ilya Bogdanov 2011-09-14T18:53:10Z 2011-09-15T04:01:02Z <p>$\def\u{{\bf u}}\def\p{{\bf p}}\def\q{{\bf q}}$ Consider all the points of intersection of the lines $L_d$ with the hyperplanes $H_k$ defining the facets $F_k$. Let $\q$ be the one closest to $\p$; suppose $\q=L_d\cap H_k$. Then $(d,k)$ is a desired pair. </p> <p>Firstly, $\q$ should belong to $F_k$, otherwise the segment $[\p,\q]$ would intersect the boundary of a polytope at a point on another facet; thus $d\in G_k$. Next, let $\q_1,\dots,\q_D$ be the intersection points of the hyperplane $H_k$ with the lines $L_1,\dots,L_D$ (some of these points may be ideal). Then $\|\p-\q\|=\min_i\|\p-\q_i\|$ which is equivalent to your relation.</p> <p><strong>EDIT:</strong> Surely, the convexity condition IS necessary.</p>