# A Claim on Typical Voronoi Cells

I am trying to prove the following claim (may be it has been proven).

Claim: Consider a set of points $\phi=\{x_1,x_2,...,x_i,...\}$ generated by a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. Then we generate the Voronoi cells with the $k$ nearest points ($k$ order Voronoi cell WiKi, Demo).

Can we claim that the expected sum area of typical cells, in which a point $x_i\in \phi$, takes part is the same for any point $\{x_1,x_2,...,x_i,...\}$?

PS: Defining expectation for a point seems tricky to me. Because the points will change with each trial. Please help to formulate the expected number of cells a point $x_i$ takes part in, as a integral. I have a similar question on the number of cells but I posted it separately in order not to put too much in one question http://math.stackexchange.com/questions/612562/poisson-point-process-ppp-and-voronoi-cells

Suggestions or a references are most welcome, thanks.

-
Why would the expectation value of the area not be independent of i? Isn't the probability measure symmetric with respect to reindexing? – Yoav Kallus Dec 19 '13 at 20:32
@YoavKallus I am not sure how to write the expectation with respect to a point. The points change with each trial so what does it mean to take expectation with respect to a point is not clear to me. Could you explain please. – MLT Dec 19 '13 at 20:37
I am the down voter. This does not appear to be a research-level question. Why can't you just take the expectation value of the area of the cell containing the i-th point? Clearly this should not depend on i. – Yoav Kallus Dec 19 '13 at 20:44
This is not a cross post. That question is not the same. This is about the area of a cell that question is about the number of cells. I came here with a question which I believe is hard for me. May be it is obvious to you so if you can explain it that would help me and I appreciate it. Thanks for the explanation. My confusion is the point has no existence. If I run another trial that point will vanish and another set of points will appear. This is my problem. Thanks. – MLT Dec 19 '13 at 20:49
There will always be an i-th point. – Yoav Kallus Dec 19 '13 at 20:54

Notice that enumeration of points is not given a priori. The Poisson point configuration is a set of points with no order on them. It also can be viewed as a measure that puts mass 1 at each configuration point. The result is that for certain enumerations the expectation of the cell sizes will misbehave.

Here is a very crude example. Let $x_1$ be the point that is closest to the origin among those with the cell area less than 1; let $x_2$ be the closest point to the origin among those with the cell area greater than 1; find $x_3$ and $x_4$ in the same manner among the remaining points, and so on. Clearly, the area sizes of all odd cells are less than 1, area sizes of all even cells will be greater than 1, so expectations clearly differ. You may say that this is a ridiculous way to label points, but it demonstrates the problem.

For many other enumerations you will have identical expectations. On the second thought, I do not know any labeling that would not introduce some bias, except random labeling in a finite volume. Maybe there is a standard way in stochastic geometry to define enumeration or the expectation of the cell area without referring to enumerations at all.

I do not know much about stochastic geometry although there are several books with that title. I hope they do not overlook this issue. For point processes per se try the book by Daley and Vere-Jones. Kingman's book on Poisson process is mostly devoted to the 1-dimensional case, but is also a nice introduction.

-
If your point process is on a torus and not the entire plane, then you can do random labeling (uniform distribution on all labelings). However, (1)this applies only to the finite-volume situation, (2)you need an additional source of randomness, (3)points sort of lose their individuality. So I edited my answer slightly. – Yuri Bakhtin Dec 20 '13 at 2:25
Answering your questions: 1)yes, this is a counterexample. 2) You want to average over all labelings, but on the plane there are infinitely many Poissonian points and infinitely many labelings on them, and there is no natural distribution on them. Of course, you can take a limit over boxes growing to infinity, then you will arrive at some notion of expected average cell size. Comparing individual points in this scheme will not work, their individuality will be lost in the averaging procedure. – Yuri Bakhtin Dec 20 '13 at 2:38
I am afraid that my example shows that his claim is wrong. – Yuri Bakhtin Dec 20 '13 at 3:08
To be clear, my comments refer to the case where the the process is symmetric under relabelling. – Yoav Kallus Dec 20 '13 at 5:20
@YoavKallus: If you try to define things precisely you will be in trouble or end up with meaningless statements. For example, what exactly do you mean by "the process is symmetric under relabelling"? In the construction of my answer I start with an arbitrary Poisson configuration and "relabel" it obtaining a labeling that violates the claim. – Yuri Bakhtin Dec 20 '13 at 14:58

The 2005 paper "Statistics of Random Plane Voronoi Tessellations" by Ken Brakke (PDF download) computes various statistics when the points follow a Poisson process, including edge-length distribution:

He quotes Gilbert for the distribution of cell areas (while Brakke computes the variance):

E. N. Gilbert, “Random subdivisions of space into crystals.” Annals of Mathematical Statistics. 33 (1962), 958–972.

-
Thank you Joseph. But I am seeking to establish the claim. Distributions and moment data are available in tables that I found in the library. Appreciate your effort very much. – MLT Dec 19 '13 at 19:20
@MLT: Sorry for not answering your question directly. My hope is that if you study the calculations in these papers, you will be led to an answer to your question. But I do not know that for certain. – Joseph O'Rourke Dec 19 '13 at 20:06
I understood your intention :) everything helps in the end, thanks again. – MLT Dec 19 '13 at 20:08