Voronoi cell volume inside the ball

I have the following problem:

Let us denote a ball with center $C$ and radius $R$ in $\mathbb{R}^d$ as $B(C, R)$. Given a unit ball $B(0, 1)$ and vector $u$ has a uniform distribution inside the ball: $u \sim U(B(0, 1))$. Then we sample $M$ points $v_1, \dots, v_M$ that are uniformly distributed in the ball $B(0, 1)$ and the distance between $u$ and $v_i$ is not greater than $r$, that is $v_i$ are i.i.d. in $B(0, 1) \cap B(u, r)$. How to estimate the volume of the Voronoi cell of $u$ inside the ball $B(0, 1)$? I need an upper bound here.

I can obtain only very rough estimates which do not depend on the dimension of the space $d$ and radius $r$. It is clear that the desired values are growing monotonically as $r$ growing and if we put $r \ge 2$, then $v_1, \dots, v_M$ are uniformly distributed inside the ball $B(0, 1)$. So, $u, v_1, \dots, v_M$ are i.i.d. and uniformly distributed in $B(0, 1)$. The rigorous definition of the value that I need to estimate (up to a scaling factor of the volume of unit ball): $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) $$ It is clear that $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}$ = $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_i | q \sim U(B(0,1))\}$, so the expectations of all volumes are equal and the sum of all volumes is equal to $1$. Hence $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) = \frac{1}{M+1}$$ It remains only to multiply it by the volume of unit ball.

But as $r$ becomes less than $2$ the volume decreases, so would like to obtain estimates which take it into account. Moreover, I performed numerical experiments which shows that the estimation also should depends on the dimension of the space $d$. Here is normal and log scale plots ($M = 10$):

In the more general case when $r < 2$ we still have that $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_j | q \sim U(B(0,1))\}$ = $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_k | q \sim U(B(0,1))\}$ and the sum of such probabilities for $u$ and $v_1, \dots, v_M$ is equal to $1$, so we have: $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) + M \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_1 | q \sim U(B(0,1))\}) = 1$$

If we were able to find another equation or estimation on the ratio of volumes, then the problem would be solved.

I would very appreciate any your help, ideas, papers, books and so on. Thank you for your help!

UPD: Also it is possible to directly write down the required value as an integral. It is easy to see that the probability $\mathbb{P}(\rho(q, u) < \rho(q, v_i))$ correspond to the volume of spherical cap, it only remains to find the height of this spherical cap. My calculations showed that if $\|u\| \le \|v\|$ then $$ h = 1 - \dfrac{\|v\|^2 - \|u\|^2}{2\|v-u\|} $$ $$ \mathbb{P} = 1 - \frac{1}{2} I_{2h - h^2}(\frac{d+1}{2}, \frac{1}{2}) $$

and if $\|u\| \ge \|v\|$ then $$ h = 1 - \dfrac{\|u\|^2 - \|v\|^2}{2\|v-u\|} $$ $$ \mathbb{P} = \frac{1}{2} I_{2h - h^2}(\frac{d+1}{2}, \frac{1}{2}) $$

where $I_x(a, b)$ is incomplete regularized beta function.

One more observation is:

$$\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u\} = \mathbb{P}(\rho(q, u) < \rho(q, v_i), i=1,\dots,M) = \prod\limits_{i=1}^{M}\mathbb{P}(\rho(q, u) < \rho(q, v_i)) = (\mathbb{P}(\rho(q, u) < \rho(q, v)))^M$$

since $v_1,\dots,v_M$ are i.i.d.

So now we can integrate for $u$ and $v$ and obtain the desired value:

$$ \frac{1}{Vol(B(0,1))} \int\limits_{u \in B(0,1)} \Big( \int\limits_{v \in B(0,1) \cap B(u, r), \|v\| \le \|u\|} (\frac{1}{2}I_{2h-h^2}(\frac{d+1}{2},\frac{1}{2}))^M \frac{1}{Vol(B(0,1) \cap B(u,r))}dv + \int\limits_{v \in B(0,1) \cap B(u, r), \|v\| \ge \|u\|} (1 - \frac{1}{2}I_{2h-h^2}(\frac{d+1}{2},\frac{1}{2}))^M \frac{1}{Vol(B(0,1) \cap B(u,r))}dv \Big) du,$$

where $h = 1 - \frac{| \|v\|^2 - \|u\|^2 |}{2\|v-u\|}$

The first summand here is about $\frac{1}{2^M}$ since regularized incomplete beta function is bounded by $1$, so it remains only to estimate the second summand.

If I was able to estimate the asymptotics of this integral, it would solve my problem!

Solution 1:

Not a full solution but too long for a comment:

For $r \ll 1$, volume of $B(u,r) \ll$ volume of $B(0,1)$ (esp. if $d$ is high), so an approximation might be available:

(1) $P(B(u,r) \subset B(0,1)) \approx 1$, which enables us to simplify $B(0,1)\cap B(u,r) = B(u,r)$, preserving the symmetry of the distribution of $v_i$.

(2) $P(q \in B(0,1) - B(u,r)) \approx 1$.

Now, $q \in Voronoi(u)$ iff $\forall i: dist(q,u) < dist(q,v_i)$. Assuming (1) & (2), we can say:

(3) $P(dist(q,u) < dist(q,v_i)) \approx 1/2$, since about half of $B(0,1)\cap B(u,r) = B(u,r)$ is closer to $q$ than $u$ is. [Consider the hyperplane through $u$ which is $\perp$ to the line segment $L$ from $u$ to $q$. The hyperplane bisects $B(u,r)$ into two half-balls. Any $v_i$ in the half-ball away from $q$ satisfies $dist(q,v_i) > dist(q,u)$. In fact even in the half-ball on the same side of $q$ there are some $v_i$ satisfying $dist(q,v_i) > dist(q,u)$, but if $r \ll 1$ then with high prob $r \ll |L|$ i.e. $q$ is "far away" from $u$ so the approximation should be good.]

(4) $P(q \in Voronoi(u)) \approx 1/2^M$, since the $v_i$ are independent.

This approximation should be pretty good for $r \ll 1$ and esp. at high $d$, because the ratio of volumes goes as $r^d$. E.g. you seem to have simulated the case of $r=0.1, d = 5$ and I wonder if it's accurate there. (I couldn't check the graph myself since you didn't mention what $M$ you used.)

BTW, this approximation totally ignores the part of $Voronoi(u)$ that is actually inside $B(u,r)$. Effectively we're saying any such part of the Voronoi cell will be too small to matter, and instead the expected volume is almost entirely made of the rare cases when a large portion of $B(0,1)$ is available as $Voronoi(u)$ because all the $v_i$ happen to be picked from "the other side". However, this kind of approximation may break down when $M$ is very large, as the $1/2^M$ term becomes tiny and the part of $Voronoi(u)$ inside $B(u,r)$ might become the dominant (but still very small) term.

For intermediate values of $r, d, M$, the problem seems very difficult to solve exactly, but the intuition probably still kinda holds. The key factor is probably the volume ratio $r^d$, although now that $B(u,r) \cap B(0,1)$ is not a ball it significantly complicates matters. But at least this may give an idea why for higher $d$ the probability is closer to the low value ($1/2^M$) but for lower $d$ the probability is closer to the $1/(M+1)$ value.

BTW are you seriously interested in all possible $r,d,M$? If in your application you have certain ranges that are of more interest there might be better solutions / approximations available. (E.g. the case of $M=1$ might be exactly solvable...)