0

I am wondering if any convex geometers/probabilists have looked at the following question:

Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each point $x_i\in\{x_1,\ldots, x_n\}$, draw $N$ points uniformly on the sphere $S^{d-1}$ with radius $r>1$ centered at $x_i$, denote as $x_{i, 1}, \ldots, x_{i, N}$. Let $C$ be the convex hull of $x_{1,1}, \ldots, x_{1,N},\ldots, x_{n,1},\ldots,x_{n,N}$. What is the probability that $\forall i\in\{1,\ldots, n\}$, $B(x_i, 1)\in C$?

So in other words, for every original point $x_i$, we draw a unit ball around it, how likely that $C$ contains all these unit balls?

I found Probability that a convex shape contains the unit ball was asking a similar question. According to the comments, if $N$ is exponential in $d$, then my question holds with probability $1$, because for each $i$, the convex hull of $x_{i, 1},\ldots, x_{i, N}$ already contains a unit ball. My question is different that we have $n$ points, and I imagine the neighboring vertices help each other to enlarge the convex hull. So perhaps a tighter bound exists?

Has this problem been studied before? What are the assumptions that people put on the distribution of $x_i,\ldots, x_n$? Thanks for any comments/answers!

$\textbf{Update:}$ what if we make the original n points to be d+1 points that make a regular $d$-simplex?

user3799934
  • 133
  • You may well ask "what assumption to put there". There is no such thing as a "randomly distributed point in $\mathbb R^d$". There are points distributed according to particular probability distributions. – Robert Israel Jun 15 '18 at 05:20
  • @RobertIsrael Hi thanks for your comments. What I try to say is, I'm not sure what distribution people assume in the literature. For example, one thing that might be taken into account is the number of extreme points. https://link.springer.com/chapter/10.1007/978-3-540-30140-0_25 first assumed each dimension is independent. Later they use smoothed analysis where the actual distribution doesn't matter anymore. There are also papers on this topic use different assumptions. I would like to see any reference despite what the assumption is. – user3799934 Jun 15 '18 at 07:04
  • Here is an idea that may help. Draw a tangent plane to the unit sphere that cuts off a cap of the sphere of radius r. If there are no perturbed points in this cap, then the convex hull shaves off some of the unit sphere. Now the idea is to ask if enough of the points on the r-sphere fill enough of the caps on the side opposite from the simplex. Gerhard "Maybe Look On The Outside" Paseman, 2018.06.24. – Gerhard Paseman Jun 25 '18 at 02:52

0 Answers0