Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does anyone know the probability distribution of the shapes of Delaunay triangles in a constant-intensity Poisson process in the plane?

Slightly later edit: One can imagine performing the experiment repeatedly and looking at the one triangle that surrounds the origin, and ask, for example, how frequently it will be obtuse; or one can imagine doing it just once and looking at all of the infinitely many triangles and asking what proportion of them are obtuse. One would (or at least I would) initially guess the two answers are the same (and similarly for other sets of shapes besides the set of all obtuse triangles). One complication in proving that would be that the shapes of the infinitely many triangles one gets by doing the experiment once are not mutually independent.

share|improve this question
2  
I wouldn't expect these two to be the same, since the first one samples them according to their area and the second one according to their number, and I'd expect there to be a correlation between the area of a triangle and its obtuseness. When you ask about "the probability distribution of the shapes", I would take that to mean the second one, not weighted by area. (It's a nice question, by the way :-) –  joriki Dec 26 '11 at 5:02
    
@joriki : Thank you. Your comment also raises a good question. Or maybe several. I'm going to guess that the shape is conditionally independent of the size given the value of some statistic that reports something about how crowded the neighborhood is. But I'm not very sure of that. –  Michael Hardy Dec 26 '11 at 5:44
    
Here's a funny thing, and I wonder if there's some name for it: When a stochastic process consists of a sequence $X_1,X_2,X_3,\ldots$ of random variables, one can say of two realizations $X_1(\omega_1),X_2(\omega_1),X_3(\omega_1),\ldots$ and $X_1(\omega_2),X_2(\omega_2),X_3(\omega_2),\ldots$ that $X_{34}$ has one value in one case and another in the other case, but if one runs the Poisson experiment above twice, one cannot say that a certain Delaunay triangle---say the "34th" one (whatever that might mean)---has one value in one case and another value in the other. –  Michael Hardy Dec 26 '11 at 5:53
    
@MichaelHardy: Given a realization of a point process on $\mathbb R$, the standard order in $\mathbb R$ induces an order on the points, and if the number of points is countable, picking one of them as "point 0" then gives a natural order isomorphism with $\mathbb Z$ (and we may then even be able to characterize the process in terms of this order). $\mathbb R^2$, however, has no natural order that would let us do that. –  Ilmari Karonen Dec 26 '11 at 6:48
    
@IlmariKaronen We have a quite nice order on $\mathbb{R}^2$ that can be used to order the points of the Poisson experiment (an consequently the triangles). We just have to order the points by their distance from the origin and if they have same distance we order them by their angle with fixed direction (we just consider polar coordinates). –  Gilles Bonnet May 10 at 11:23

3 Answers 3

As the paper is quite long and sometimes technical, here's the gist of the calculation:

Assuming we've somehow dealt with the infinite extension of the plane and the resulting unnormalizability of distributions over "all possible configurations" (which the paper does), we can say that the "distribution" of relative configurations of $3$ points $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$ is uniform with respect to the volume element in the four-dimensional space of Cartesian coordinate differences $(\Delta x_2,\Delta y_2,\Delta x_3,\Delta y_3)=(x_2-x_1,y_2-y_1,x_3-x_1,y_3-y_1)$. We can then transform to the "circumdisk representation" $(x_i,y_i)=(x_0,y_0)+R(\cos\theta_i,\sin\theta_i)$, where the circumcentre $(x_0,y_0)$ cancels in the coordinate differences, and calculate the Jacobi determinant:

$$ \begin{eqnarray} \left| \frac{\partial(\Delta x_2,\Delta y_2,\Delta x_3,\Delta y_3)}{\partial(R,\theta_1,\theta_2,\theta_3)} \right| &=& \left| \begin{array}{cccc} \cos\theta_2-\cos\theta_1&R\sin\theta_1&-R\sin\theta_2&0\\ \sin\theta_2-\sin\theta_1&-R\cos\theta_1&R\cos\theta_2&0\\ \cos\theta_3-\cos\theta_1&R\sin\theta_1&0&-R\sin\theta_3\\ \sin\theta_3-\sin\theta_1&-R\cos\theta_1&0&R\cos\theta_3\\ \end{array} \right| \\ &=& R^3\left(\sin(\theta_1-\theta_2)+\sin(\theta_2-\theta_3)\sin(\theta_3-\theta_1)\right)\\ &=&\pm4R^3\sin\alpha\sin\beta\sin\gamma\;, \end{eqnarray} $$

where $\alpha,\beta,\gamma$ are the angles of the triangle formed by the three points. Thus the "distribution" factorizes into radial and angular parts. As Michael pointed out in a comment under the answer on MO, the angular part is proportional to the ratio of the area of the triangle to the area of the circumcircle, so the more of its circumcircle it occupies, the more likely a triangle is to appear.

Note that this is all about general triangles and doesn't refer to Delaunay triangles yet, so for instance if we consider all triangles with circumradii in a certain range, their angles are distributed according to $\sin\alpha\sin\beta\sin\gamma$. Since a triangle formed by any three points is a Delaunay triangle iff its circumcircle doesn't contain any other points, the distribution for Delaunay triangles is proportional to the above result times the exponential factor $\exp (-\pi\rho R^2)$ (with $\rho$ the intensity of the Poisson process) to account for the probability of the circumcircle being empty.

Incidentally, if we follow Michael's first prescription and consider the distribution for the triangle surrounding the origin, we have to multiply by the same area factor again, so the angular distribution in this case is proportional to $\sin^2\alpha\,\,\sin^2\beta\,\,\sin^2\gamma$.

share|improve this answer
up vote 2 down vote accepted

Since no one answered here, I posted this question to mathoverflow, where Igor Rivin posted this answer, which I "accepted":

See this paper of R. E. Miles (he has plenty of related results for points on the sphere, etc, etc, mathscinet will tell you more). The results you want are in section 9 (p. 112, and thereabouts). (the paper is: On the homogeneous planar Poisson point process, R. E. Miles, Mathematical Biosciences 6 (1970).

share|improve this answer

Take a look in the relevant chapter of "Spatial Tessellations" by Okabe et al. They give explicit distribution functions for a pair of angles of a random triangle in a Poisson Delaunay Tessellation, and there's also a 'bell diagram', giving the distribution of shapes and their frequencies.

If you don't have the book, I think the distribution function also appears in the paper "The Expected Extremes in the Delaunay Triangulation" - Eppstein et al.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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