# Estimate the volume of Voronoi cell

Let given a ball of radius $\alpha$ centered in point $u$ in $d$-dimensional space. Let given a sample of $n$ uniformly distributed vectors $x_i$ ($i = 1,\dots,n$) inside the ball. For each vector $x_i$ we connect points $u$ and $x_i$ by a segment and build a hyperplane $P_i$ through the middle of the segment and orthogonal to it. In the general case, the constructed hyperplanes bound a polyhedron in $\mathbb{R}^d$. I need to estimate from above the probability that uniformly distributed vector $q$ fall into this polyhedron.

In some cases the constructed polyhedron can be unbounded. More precisely, as far as I know it can be if and only if $u$ is not contained in the convex hull of $x_i$. This probability can be estimated, see for example here. Then I can write down

$\mathbb{P}( q$ in polyhedron $) \le \mathbb{P}(u$ in convex hull$) \mathbb{P}(q$ in polyhedron$|u$ in convex hull$) + \mathbb{P}(u$ not in convex hull$) \mathbb{P}(q$ in polyhedron$|u$ not in convex hull$) \le \mathbb{P}(q$ in polyhedron$|u$ in convex hull$) + \mathbb{P}(u$ not in convex hull$)$.

In such a way the problem of an unbounded polyhedron is overcome and we only need to estimate $\mathbb{P}(q$ in polyhedron$|u$ in convex hull$)$.

One more idea is that w.l.o.g. we can assume that $x_i$ is uniformly distributed on the sphere. Then we know the radius of sphere inscribed in our polyhedron, which is exactly equal to $\alpha / 2$.

There is another interpretation of this problem, maybe it can help. It is easy to see that our polyhedron is exactly the Voronoi cell of point $u$, so we need to estimate the volume of Voronoi cell.

It is obvious that when $n$ tends to infinity, then polyhedron volume tends to zero, so there has to be some rate of converges, but I do not know how to estimate it.

Thank you very much for any ideas, proofs, estimates, papers and so on!

• Are you still interested in this problem? For a recent paper I've studied this problem, where $n=\exp \Theta(d)$ and I wanted to know the size of the enclosed region. Short answer: denoting $\alpha=n^{1/d}$, the enclosed polyhedron $P$ has volume relative to the unit ball $B$ given by $$\mathrm{vol}(P)=\left(\frac{\alpha^2}{4\alpha^2-4}\right)^{d/2+o(d)}\mathrm{vol}(B).$$ This assumes $\alpha \leq \sqrt{2}$; for larger $\alpha$ we essentially have $\mathrm{vol}(P) = \mathrm{vol}(B) / n$ up to order terms. This directly gives you the probability that a uniformly random point in $B$ is in $P$. – TMM Jun 2 at 1:00

A partial answer. Let us remove some syntactic sugar: we may clearly assume $\alpha=1$ and $u=0$.
Given our $n$ random points $x_i$, in the general case they define a polyhedron enclosing the origin whose volume is lower-bounded by $V(1) \left(\frac{1}{2}\min\|x_i\|\right)^d$, with $V(1)=\frac{\pi^{d/2}}{\Gamma(1+d/2)}$ being the volume of the $d$-dimensional unit ball. On the other hand the distribution of $\min\|x_i\|$ is fairly simple to compute. The PDF of $\|x_i\|$ is supported on $(0,1)$ and given by $f(x)= \frac{1}{d} x^{d-1}$, hence the PDF of $\min\|x_i\|$ is supported on $(0,1)$ and given by $g(x)=ndx^{d-1}(1-x^d)^{n-1}$. It follows that on average $\min\|x_i\|$ equals $\frac{\Gamma(n+1)\Gamma(1/d)}{d\,\Gamma(n+1+1/d)}$, while the expected value of $\left(\min\|x_1\|\right)^d$ simply equals $\frac{1}{1+n}$.
A reasonable upper bound is of the form $\frac{1}{n+1}\left(1+\frac{C_d}{\sqrt{n}}\right)$ (approximately $2^d$ times the lower bound), since our $n$ points, together with the origin, divide the hypersphere in $n+1$ Voronoi cells, which are expected to be roughly of the same volume (with their volumes being approximately normally distributed). Numerical simulations should find the $C_d$ constant with a reasonable accuracy.