n-simplex in an intersection of n balls

Question

Consider a $n$-simplex, $n \geq 2$ with vertices $x_i,i=1,...,n+1$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ in the simplex. The question: is $x_0$ in at least $n$ balls?

Some notes. It is impossible to make the question stronger by claiming that there is vertex $i=i(x_0)$ such that $x_0$ is in all balls $B_{ij},j \neq i$. Also, it is not true for $n+1$ balls (there are counterexamples for both cases if $n=3$).

Also, $x_0$ is in ball $B_{ij}$ if and only if $\angle x_ix_0x_j \geq \pi/2$, or equivalently, vertices $x_i$ and $x_j$ are on opposite sides of the hyperplane $H_i$ that contains $x_0$ and is orthogonal to the line through $x_i$ and $x_0$ (and similarly for $H_j$).

Also, this question is a stronger version of that question (Thanks to Alex Ravsky for solving it).

Any help is much appreciated. Thank you.

"Also, $x_0$ is in ball $B_{ij}$ if and only if $\angle x_ix_0x_j \geq \pi/2$, or equivalently, vertices $x_i$ and $x_j$ are on opposite sides of the hyperplane $H_i$ that contains $x_0$ and is orthogonal to the line through $x_i$ and $x_0$ (and similarly for $H_j$)." -- How do you prove this? — jkn, Aug 26 '13 at 17:09
The first part holds because $x_i$ and $x_j$ are antipodal. The second holds because the hyperplane $H_i$ is orthogonal to the line through $x_i$ and $x_0$. — Max, Aug 26 '13 at 17:13
I'd suggest you choose another name for the sample point $x_0$, since $x_0$ is already a vertex of the simplex. — Christian Blatter, Aug 26 '13 at 19:13

score 15 · Accepted Answer · answered May 10 '14 at 18:25

I will use the notation $\mathbf{v}_i$ for the vector from $x_0$ to $x_i$.

Assume that $x_0$ is in the interior of the simplex. (By continuity, the statement will extend to boundary points.) Then there are some positive weights $w_1,\ldots,w_{n+1}>0$ such that $\sum\limits_{i=1}^{n+1} w_i \mathbf{v}_i=\textbf0$.

Let us build a graph on the vertices $1,\ldots,n+1$. Let the vertices $i$ and $j$ be connected if $x_0$ is inside the ball with diameter $x_ix_j$; in other words, if $\mathbf{v}_i\cdot \mathbf{v}_j\le0$.

We show that this graph is connected. Assume the contrary; then the vertices can be split in two disjoint nonempty sets, say $A$ and $B$ such that $A\cup B=\{1,2,\ldots,n+1\}$. Since there is no edge between the two vertex sets, we have $\mathbf{v}_i\cdot \mathbf{v}_j>0$ for all $i\in A$ and $j\in B$.

Consider $$ 0 = \left(\sum_{i\in A\cup B} w_i \mathbf{v}_i \right)^2 = \left(\sum_{i\in A} w_i \mathbf{v}_i \right)^2 + \left(\sum_{i\in B} w_i \mathbf{v}_i \right)^2 + 2\sum_{i\in A}\sum_{i\in B} w_iw_j(\mathbf{v}_i\cdot \mathbf{v}_j). $$ In the last sum all terms are positive, contradiction. Now we have proved that the graph is connected.

A connected graph on $n+1$ vertices has at least $n$ edges, so at least $n$ balls contain $x_0$. Done.

really elegant! I was thinking about this problem for a while but could no get a clue of a proof. Can I ask how did you come up with these ideas? — Gilles Bonnet, May 10 '14 at 20:09
Gilles: I think using vectors and dot products is standard. First I proved that there is a good ball at every vertex, but this gave only $(n+1)/2$. So I considered other distributions of the vertices. At the end I realized that we have such a graph. — G.Kós, May 11 '14 at 15:34
This problem (and your nice solution) was used in problem 5 in the 2015 IMC. — Winther, Feb 18 '16 at 02:18

Gilles Bonnet · Answer 2 · 2014-05-10T09:34:52.880

This does not answer the question. I don't prove anything here but just present the result of some simulations that suggest the answer to the question is yes.

My experience make me being careful about my intuition when it is about to think about geometrical construction in more then $3$ dimensions. So before investigating more this question I wanted to check if there is no counter example I could get with Mathematica. I generated some random simplices with a random point inside and counted the number of balls covering the inside point. For all the tests I did, no counter example appeared. Moreover, the distribution of the number of balls in my simulations seem to be close to a normal distribution.

For example, I generated $1000$ random $3$-dimensional simplices as the convex hull of $4$ random points uniformly distributed in the unit cube. For each simplex I generated $1000$ random inside points with baricenter coordinate uniformly distributed. Below this is the histogram of the number of balls covering the inside points considered. We observe that it starts at $3$, which means we did not find counter example to the conjecture.

dimension$=3$; number of edges$={4 \choose 2}=6$.

Below I give more histograms obtained from simulations in higher dimension. For each I generated $100$ random simplices and and tested $100$ random inside points.

dimension$=4$; number of edges$={5 \choose 2}=10$.

dimension$=5$; number of edges$={6 \choose 2}=15$.

dimension$=6$; number of edges$={7 \choose 2}=21$. enter image description here

dimension$=7$; number of edges$={8 \choose 2}=28$. enter image description here

dimension$=8$; number of edges$={9 \choose 2}=36$. enter image description here

dimension$=20$; number of edges$={20 \choose 2}=190$. enter image description here

The code I used with Mathematica (it can certainly be optimized if you wanna run biger simulations)

> RandomSimplex[dim_] := RandomReal[{0, 1}, {dim, dim + 1}]
> RandomBaricenter[dimension_] := Module[{baricenter},
>     baricenter =  RandomReal[{0, 1}, dimension + 1];
>     baricenter =  baricenter/Sum[baricenter[[i]], {i, 1, dimension + 1}];(*normalisation*)
>     Return[baricenter]]
> Distance[A_, B_] := Module[{dim},
>     dim = Dimensions[A][[1]];
>     Return[Sqrt[Sum[(B[[i]] - A[[i]])^2, {i, 1, dim}]]];]
> NumberClosePoints[simplex_, point_] :=   Module[{dim, number, i, j, M, A, B},
>     dim = Dimensions[simplex][[1]];
>     number = 0;
>     For[i = 1, i <= dim, i++,
>         For[j = i + 1, j <= dim + 1, j++,
>         A = Transpose[simplex][[i]];
>         B = Transpose[simplex][[j]];
>         M = (A + B)/2;
>         If[Distance[M, A] > Distance[M, point], number++,]]];
>     Return[number]]

and to run the tests and produce and histogram:

> dimension = 3;
> nBar = 1000;(*number of barycenter tested*)
> nSimplices = 1000;(*number of simplices tested*)
> list = {};
> For[i = 1, i <= nBar, i++,
>   bar = RandomBaricenter[dimension];
>   For[j = 1, j <= nSimplices, j++,
>     simplex = RandomSimplex[dimension];
>     point = simplex.bar;
>     n = NumberClosePoints[simplex, point];
>     list = Append[list, n];
>     If[n < dimension, Print[{bar, simplex, n}],]];]
> Histogram[list]

n-simplex in an intersection of n balls

2 Answers2