I am considering a Voronoi tessellation in the unit square $V \in [0,1]^2$ for $G$ points uniformly randomly distributed. Then I am considering $N$ other points also randomly distributed uniformly in $V$ (and independently of $G$), and I want to find an expression for the p.d.f. of the counts of these points in the Voronoi cells, as I change $G$ and $N$.

This is how I am reasoning. Because $G\gg 1$ in my case, I can approximate the distribution of Voronoi cell areas by the Gamma distribution $\mathrm{Gamma}(x;\nu;\nu^{-1})$ [Kiang, 1966], where $x$ is the cell area $s$ normalized w.r.t. the mean cell area $\rho^{-1}$, i.e. $x=\rho s$. Moreover, following [Pineda et al., 2006], I get an excellent fit for my data when $\nu=3.575$.

Now the harder part. In the classical paper by Gilbert [1962,p. 963], it is reasoned that the probability of a randomly-picked point in the plane to belong to a cell of area $s$ is $p^*(s)=\rho s \cdot p(s)$ where $p(s)$ is the p.d.f. of cell areas, i.e. $\mathrm{Gamma}(\rho s; \nu, \nu^{-1})$ in my case. Once again, it is convenient to work in terms of the normalized cell area $x$, whereby I can define the p.d.f. that given one point, it belongs to a cell of size $x$, by $f(x|n=1)=x\cdot \mathrm{Gamma}(x;\nu,\nu^{-1})$.

If everything worked out fine, the probability that $k$ randomly-picked points belong to the same cell of size $x$ would then be $f^k(x|n=1)$ (because of the independent drawing). Moreover, assuming that $f(k|x)$ - the probability that given a cell of size $x$, it contains $k$ points randomly-drawn from $N$ - is a $\mathrm{Binomial}(k,N,x)$, it would follow that $f_k(k) = f(k|x) p(x)f^{-k}(x|n=1)$.

This reasoning is apparently seriously wrong. But I cannot figure out where I am wrong. If then everything makes sense up to this point, what am I missing/doing that I cannot correctly fit my data?


Ok, I did not find an analytical formula for the above, except for an integral expression, obtained by marginalizing $f(k,x)$, since there is not a direct way to compute $f(x|n=k)$, that is the p.d.f. that a cell of size $x$ contains at least $k$ points. So in my case, $f_k(k) = \int_0^G f(k|x)f(x)dx$ provides a correct estimation for the distribution of random points in a Voronoi cell in a random tessellation of $G$ cells in unit square.

Note: $f(x|k)$ is not trivial to estimate, because it certainly relates to the probability that $k$ independent points are each found in a cell of size $x$, i.e. $f^k(x|1)$, but in addition, we also need to estimate the probability that such cell is the same for all $k$ points, or in other words, the probability that randomly picking $k$ points, the all fall in the same cell.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.