Group Abstract Group Abstract

Message Boards Message Boards

Statistical distributions of areas of Voronoi cells

Attachments:
DOWNLOAD-DESKTOP...nb
POSTED BY: Vitaliy Kaurov
10 Replies
Sort By:

You may be interested in this paper, which takes a semi-empirical approach to come up with a closed-form approximate formula:

At the time when it was written, Mathematica did not have VoronoiMesh, but one could "trick" it to quickly compute a Voronoi tessellation by using ListDensityPlot with InterpolationOrder -> 0 and extracting the polygons.
POSTED BY: Szabolcs Horvát
BJ Miller
BJ Miller, Advisian
Posted 7 years ago

Very Nice. I am aware that the distribution of Lightning strike intensity from a Thunderstorm also closely follows a Gamma Distribution. Could this be due to cells of charge inside the cloud which organise like a Voronoi topology? Does a Gamma distribution also arise from a 3 D distribution of volumes of a Vornoi tesellation?
POSTED BY: BJ Miller
Erik Mahieu
Erik Mahieu
Posted 7 years ago

Thanks for sharing everybody! Maybe this can add some more information:

In the article "Statistical Distributions of Poisson Voronoi Cells in Two and Three Dimensions" by Masaharu Tanemura, mentioned by Marco Thiel, the distribution of the perimeter of the cells (and the number of edges etc.) is also analyzed. Here I adapted the code of Vitaly to perimeters and we see (as in the article) that now we have a normal distribution:

perimeters = Perimeter /@ vorInner;
hist = Histogram[perimeters, Automatic, "PDF", 
   PlotTheme -> "Detailed"];
dist = FindDistribution[perimeters]
Show[hist, Plot[PDF[dist, x], {x, 0, .1}]]

enter image description here

And for the number of edges, we find a BinomialDistribution with FindDistribution although the result look almost "normal" as we use EstimatedDitribution

numberOfEdges[poly_] := Length[First@poly]
edges = numberOfEdges /@ vorInner;
histE = Histogram[edges, Automatic, "PDF", PlotTheme -> "Detailed"];
distE = EstimatedDistribution[edges, 
  NormalDistribution[\[Mu], \[Sigma]]]
Show[histE, Plot[PDF[distE, x], {x, 0, 12}]]
distEB = FindDistribution[edges]
Plot[CDF[distEB, x], {x, 0, 12}, Filling -> Bottom]

enter image description here
POSTED BY: Erik Mahieu

Great, @Erik, thanks for exploring further and sharing!
POSTED BY: Vitaliy Kaurov
POSTED BY: Marco Thiel

@Marco Thiel thank you for the references and insight! I believe FindDistribution, while finding correct distributions, needs some tune up to get the distribution parameters right. To test the waters, I tried using EstimatedDistribution and got a bit better results. Let's run this for 500,000 points:

pts=RandomPoint[Disk[],500000];
mesh=VoronoiMesh[pts,PerformanceGoal->"Speed"];
vor=MeshPrimitives[mesh,2]
vorInner=Select[vor,RegionWithin[Disk[],#]&];
areas=Area/@vorInner;
hist=Histogram[areas,200,"PDF",PlotTheme->"Detailed"];

and then find the parameters assuming distributions are known:

disGAM = EstimatedDistribution[areas, GammaDistribution[a, b]]

GammaDistribution[3.526166220777205, 1.7809806247800413*^-6]

disEXT = EstimatedDistribution[areas, ExtremeValueDistribution[a, b]]

ExtremeValueDistribution[4.775094275466527*^-6, 2.5746412541824736*^-6]

We see gamma (red) behaves a bit better now, both for zero and for the tail values:

Show[hist,Plot[{PDF[disEXT,x],PDF[disGAM,x]},{x,0,.00002},PlotStyle->{Blue,Red}]]

enter image description here

But while p-value of gamma is greater than extreme, it is still pretty low, not sure if there is a catch here somewhere:

DistributionFitTest[areas,disGAM]

0.000051399258187534436`

DistributionFitTest[areas,disEXT]

0.`
POSTED BY: Vitaliy Kaurov

I don't find it all that surprising that the result is a Gamma distribution. The 1-d case is well known as it is the distribution of interarrival times of a Poisson process and is exponentially distributed. The exponential distribution is a special case of the Gamma so maybe you're onto something.
POSTED BY: Carlo Barbieri

Very nice. Thanks for sharing. Some years ago I did this with 10^9 cells. If I recall correctly the left side is a bit higher (more probably) than a gamma distribution.

To remove any edge-effects, what people do is: take random points in a square, and then copy the square 9 times in a 3*3 grid, such as to emulate period boundary conditions. Then take only the polygons which center is in the center unit square…

Great stuff!

–SH
POSTED BY: Sander Huisman

Thanks! Awesome idea about edge-effects! Did you estimate any analytical models beyond Gamma or it was just pure empirical thing?
POSTED BY: Vitaliy Kaurov

I looked at different things: how many sides, angles, area, perimeter, and many conditionally averaged quantities. But area of the PDF as well. But no analytical shape is known for it. I believe that there is something known for perimeter.

POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard