4
$\begingroup$

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.

  • 0
    @GillesBonnet : . . . but not in the sense I had in mind.2014-05-10

3 Answers 3

1

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.

4

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$.

2

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).