MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


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|cite|improve this question
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
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|cite|improve this answer
Thanks Ilya Bogdanov for this nice and clear solution. – han Sep 15 '11 at 9:55

Your Answer


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.