3
$\begingroup$

When I read research article: here, I found following set-up:
Figure illustration of one realization of Big node (BN) positions from the homogeneous Poisson point process (PPP) and of small nodes (SN) uniformly distributed in the corresponding Poisson-Voronoi cells. Each SN connects to its closest BN such that the coverage area of a BN is its Poisson-Voronoi cell. The SNs are assumed to be uniformly distributed in the Poisson-Voronoi cell of their serving BN.

However, I do not really understand the meaning of ``The SNs are assumed to be uniformly distributed in the Poisson-Voronoi cell of their serving BN".

Can someone elaborate this explanation much simpler way?

I am not sure if someone can help me of coding this one (matlab) to get such figure.

enter image description here

$\endgroup$
1
$\begingroup$

By "uniform", they mean that the point does not tend to exist more often in some regions (of each Voronoi cell) than others. In Cartesian coordinates for a rectangular cell, this means that the x and y coordinates are independent uniform random variables, say X and Y.

It's relatively straight forward to place a point uniformly on a simple geometric object, such as a rectangle, disk, or triangle. Those links are for pages that detail how to simulate Poisson point processes, but to do that, each point is placed uniformly.

But it is a bit more complicated to do it for a general Voronoi cell. Here are two possible methods.

1) The simplest and crudest method is to bound a Voronoi cell with a rectangle or disk, then place/sample the point uniformly on the rectangle or disk. If it doesn't randomly land inside the rectangle or disk, then start again. Crude, slightly inefficient, but simple.

2) The more elegant way is to first partition (ie divide) the Voronoi cells into triangles. (For a Voronoi cell, this is easy. Each side corresponds to one side of a triangle (ie two points), where the third point is the original Poisson point corresponding to the Voronoi cell.) Given the n triangles that form the Voronoi cell, randomly choose a triangle based on the areas of the triangle (ie the probabilities are the areas renormalized by the total area of the cell). In MATLAB, you would do this:

cdfTri=cumsum(areaTri)/areaCell; %create triangle CDF 
indexTri=find(rand(1)<=cdfTri,1); %use CDF to randomly choose a triangle

Then for that single triangle, uniformly place a point on it (there are expressions for this; see below). Repeat for all (bounded) Voronoi cells.

The topic of placing a single point uniformly on a general triangle is discussed in this StackExchange post; see that for suggestions of proof. For the formulas, it cites the paper "Shape distributions" by Osada, Funkhouser, Chazelle and Dobkin, where no proof is given. Discussions on this problem can also be found here and here.

For Method 2, I have uploaded some code in both MATLAB and Python (using SciPy and Numpy). The main random placement functions are located respectively in the files funVoronoiUniform.m and funVoronoiUniform.py.

I've also included two files that empirically test those functions respectively, namely VoronoiUniformTest.m or VoronoiUniformTest.py, by empirically estimating the centroids of the Voronoi cells. To test the functions, run VoronoiUniformTest.m or VoronoiUniformTest.py with the aforementioned files in the same directory/folder.

https://github.com/hpaulkeeler/voronoi_uniform

$\endgroup$
  • $\begingroup$ Could you explain your sampling method? I would have thought you’d sample with barycentric coordinates to get uniform sampling in a triangle, but you have some square roots in there. $\endgroup$ – adfriedman Aug 27 '19 at 1:39
  • $\begingroup$ I added a link to another thread on this discussion. To place a point on a disk, you need a square root, and I understand that. I have never gone through why you need square roots for a triangle, but I am not surprised. My previous searches for the proofs for those expressions led me to that StackExchange thread. Those are the best, let's say, arguments I've seen. $\endgroup$ – Keeler Aug 27 '19 at 2:11
  • $\begingroup$ Actually, a quick Google gives me this page: extremelearning.com.au/evenly-distributing-points-in-a-triangle. The square roots sneak in the expressions under the section Other shapes. But again, I don't have the time to go through this. The problem is also found here: hbfs.wordpress.com/2010/10/05/… $\endgroup$ – Keeler Aug 27 '19 at 2:18
  • $\begingroup$ I’ve just had a quick think about the barycentric sampling, and it’s really obvious why it wouldn’t work: one vertex’s contribution would be uniformly distributed on $[0,1]$, the second would be dependent on the first’s contribution, and the third vertex’s contribution would depend on a sum of both. I’m intrigued how it is actually distributed (I’ll work on it later), but it’s not surprising it’s not uniform. $\endgroup$ – adfriedman Aug 27 '19 at 2:45
  • $\begingroup$ Right. A related thread (spoiler alert?): math.stackexchange.com/questions/563129/… $\endgroup$ – Keeler Aug 27 '19 at 9:07

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.