Distance from point to vertices of convex hull

826 Views Asked by At

let $P = \{p_1, \ldots, p_k\}$ be any $k$ points on the unit $n$-sphere in $\mathbb{R}^{n+1}$ and $p_0 = 0$ the origin. Furthermore, let $CH(P\cup \{p_0\})$ denote the (possibly degenerate) convex hull of $\{p_0, \ldots, p_k\}$.

Problem: what is the lower upper bound on $$\max_{x\in CH(P\cup \{p_0\})}\min_{i=0, \ldots, k}||p_i-x||,$$ i.e. the point in the convex hull that is farthest from a $p_i$.

Any ideas on this is greatly appreciated!

Update: the answer seems to be $1/\sqrt{2}$. Details to be checked.

1

There are 1 best solutions below

0
On BEST ANSWER

This proof works for every dimension with minor modifications.

Let $p_1$ and $p_2$ be two points on the unit circle. In the case $p_0, p_1, p_2$ form a right-angeled triangle, the point on the middle of the segment $p_1p_2$ is $1/\sqrt{2}$ away from all three vertices. This is also a minimum: let $y$ be a point in the unit disk and without loss of generality assume that $y = (0,y)$ where $y>0$. If $d(y, p_i) > 1/\sqrt{2}$ the triangle $[p_0, y, p_i]$ has one side with length 1 and two sides with length greater than $1/\sqrt{2}$. But this means that $\angle p_0yp_i < \frac{\pi}{2}$ and $p_i = ((p_i)_x, (p_i)_y)$ with $(p_i)_y < y$. This holds true for every $i$ and therefore $y$ is not contained in the convex hull of $p_0, p_1, p_2$.