Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

2011-09-14T15:28:28Z

Definitions

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})$.

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\}$.

Let $\mathbf{p}=(p_{1},\ldots,p_{D})$ be a point in $\mathbb{R}^{D}$. Define

$L_{d}=\{\mathbf{p}+\theta\mathbf{u}_{d}|\theta\in \mathbb{R}\},$

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.

For $k=1,\ldots, K$, define

$G_{k}=\{d|L_{d}\cap F_{k}\neq \emptyset\}.$

Define $f:\mathbb{R}^{D}\times\mathbb{R}^{D}\rightarrow [0,1]$ as

$f(\mathbf{x},\mathbf{y})=\frac{|\mathbf{x}^\mathrm{T}\mathbf{y}|}{\left\|\mathbf{x}\right\|\left\|\mathbf{y}\right\|}.$

My conjecture

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})\}$.

Can anyone provide a counterexample?

An illustrative example in $\mathbb{R}^2$

In particular, if we restrict ourself in $\mathbb{R}^2$, the above conjecture can be restated as follows:

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°.

The figure below gives an example.

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.

Finally, any problem reformulation is also welcome.

Answer by Ilya Bogdanov for Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

2011-09-14T18:53:10Z

$\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.

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.

EDIT: Surely, the convexity condition IS necessary.

Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample - MathOverflow

Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

Definitions

My conjecture

An illustrative example in $\mathbb{R}^2$

Answer by Ilya Bogdanov for Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample