8
$\begingroup$

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm interested in things like the expected size of Voronoi cells etc.

$\endgroup$
9
$\begingroup$

The number of $(d{-}1)$-facets of a Poisson-process Voronoi cell in $\mathbb{R}^d$ is: $6$ for $d{=}2$; $\approx 15.5$ for $d{=}3$; and $\approx 37.8$ for $d{=}4$. For references and other stats, see:

Masaharu Tanemura, "Random Voronoi Cells of Higher Dimensions." (link).

Here is an unrelated but attractive image from www.qhull.org:


  VoronoiImage
  Voronoi image by KOOK Architecture, Silvan Oesterle and Michael Knauss.

$\endgroup$
8
$\begingroup$

The expected number of sides and size of a typical cell (typical is interpreted in the sense of Palm measures which basically means what you see on average in a large ball) for the Voronoi cells of a Poisson process with constant intensity in the Euclidean plane (as well as higher dimensional Euclidean spaces) are known. See for example the book by Moller "Lectures on Random Voronoi Tesselations" (it's in the series by Springer "Lecture notes in statistics").

There are other references (which I forgot but you should be able to find easily) with quite explicit calculations for the distribution of the size of the cells and also for these things when the underlying space is the hyperbolic plane.

Some other (a bit more exotic) things are known in the Euclidean case such as the asymptotic shape of the ball, first passage time (see this article)

Some things are known about percolation on the results adjacency graph (see this article where the hyperbolic case is treated).

And there are people (including myself :)) currently thinking about random walks on these random graphs.

$\endgroup$

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.