Probability that a delaunay triangle contains the center of its circumcircle

343 Views Asked by At

A Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). https://en.wikipedia.org/wiki/Delaunay_triangulation

In the Delaunay triangulation of a Poisson point process in the plane, the probability that a triangle contains the center of its circumcircle is ?

https://en.wikipedia.org/wiki/Poisson_point_process

I know for a fact that it is not $\frac{1}{4}$ which is the probability that the center of the circle is contained within the triangle formed by three random points on the circle. I find this troubling, I don't know how the probability changes from $\frac{1}{4}$ for the delaunay triangle probability.

2

There are 2 best solutions below

0
On BEST ANSWER

Here points are being uniformly chosen not on a circle but on the plane. Additionally, they're conditioned on being Delaunay triangles, but actually that doesn't change their angular distribution because the probability of any given triangle in the Poisson point process being a Delaunay triangle depends only on the area of the circumcircle and not on the angles.

The answers to the question Distribution of shapes of Delaunay triangles contain the required angular distribution; its density is proportional to

$$ \sin(\theta_2-\theta_1)+\sin(\theta_3-\theta_2)+\sin(\theta_1-\theta_3)\;, $$

where the $\theta_1$ are the angles for the three points as seen from the centre of the circumcircle. Without loss of generality we can set $\theta_3=0$. Then the probability that $\theta_2\le\pi$, and hence $2\pi-\theta_2\gt\pi$, so that the triangle is obtuse and doesn't contain the centre of it circumcircle, is

$$ \frac{\int_0^\pi\mathrm d\theta_1\int_{\theta_1}^\pi\mathrm d\theta_2\left(\sin(\theta_2-\theta_1)-\sin\theta_2+\sin\theta_1\right)}{\int_0^{2\pi}\mathrm d\theta_1\int_{\theta_1}^{2\pi}\mathrm d\theta_2\left(\sin(\theta_2-\theta_1)-\sin\theta_2+\sin\theta_1\right)}=\frac\pi{6\pi}=\frac16\;. $$

The other two angles have the same probability to be obtuse (by symmetry), and at most one angle can be obtuse, so the probability for the triangle to be obtuse is just three times the probability for one angle to be obtuse, that is, $\frac12$.

As the result is rather nice, there may well be a more elegant symmetry argument to derive it.

Note that this is the result in the case where we uniformly randomly pick one of the Delaunay triangles, that is, where all triangles are equiprobable. (I'm glossing over questions how to define this in an infinite plane; that can be done more rigorously but without changing the answer or providing any insights.) If, by contrast, we pick a triangle by uniformly randomly picking a point (or, equivalently, since the Poisson point process is invariant under translations, taking the origin) and pick the triangle that contains that point, then we weight the triangles by area, and, as explained in my answer to the question linked to above, we get the same Jacobian factor again for the density, so the angular density in this case is the square of the one above, and the probability for an angle to be obtuse is

$$ \frac{\int_0^\pi\mathrm d\theta_1\int_{\theta_1}^\pi\mathrm d\theta_2\left(\sin(\theta_2-\theta_1)-\sin\theta_2+\sin\theta_1\right)^2}{\int_0^{2\pi}\mathrm d\theta_1\int_{\theta_1}^{2\pi}\mathrm d\theta_2\left(\sin(\theta_2-\theta_1)-\sin\theta_2+\sin\theta_1\right)^2}=\frac{\frac{3\pi^2}4-4}{3\pi^2}=\frac14-\frac4{3\pi^2}\;, $$

so in this case the probability for the triangle to be obtuse is only $\frac34-\frac4{\pi^2}\approx0.3447$, which makes sense since, for a given radius of the circumcircle, obtuse triangles tend to have less area than acute triangles. You can see this when looking at an instantiation of the process:

Delaunay triangulation

At first sight (at least to me), it looks like most of the triangles are acute, because the eye is drawn towards the bigger ones, but if you look more closely, you find that many of the smaller ones are obtuse.

0
On

I don't think you understand what was claimed in lecture (or, perhaps, that your lecturer is saying false things).

If you look at the picture from the wikipedia page showing an $11$-triangle DT, you can count the number of centers that are in the associated triangle --- it turns out that $7$ of them are. So the probability, for a randomly selected triangle, that it contains its delaunay center (for this example triangulation at least) is $7/11$, not $1/2$. Either the lecturer made a mistake, or the lecturer meant something different from what you've understood.