Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

alt text

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.

share|improve this question
1  
Your conjecture (at this writing) asserts what appears to me to be an obvious equality, and says nothing about the maximum value with respect to d. You might edit your conjecture to be more in align with your example. Gerhard "Ask Me About System Design" Paseman, 2011.09.14 –  Gerhard Paseman Sep 14 '11 at 15:46
    
In case Gerhard's point isn't clear, your conjecture has the form, $c = \max \lbrace a, b, c, d, e, \ldots \rbrace$: it only states that the max of a finite set of numbers is one of the numbers. –  Joseph O'Rourke Sep 14 '11 at 16:04

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks Ilya Bogdanov for this nice and clear solution. –  han Sep 15 '11 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.