44
$\begingroup$

On a disk, choose $n$ uniformly random points. Then draw the smallest circle enclosing those points. (Here are some algorithms for doing so.)

The circle may or may not lie completely on the disk. For example, with $n=7$, here are examples of both cases.

enter image description here

enter image description here

What is $\lim\limits_{n\to\infty}\{\text{Probability that the circle lies completely on the disk}\}$?

Is the limiting probability $0$? Or $1$? Or something in between? My geometrical intuition fails to tell me anything.

The case $n=2$

I have only been able to find that, when $n=2$, the probability that the smallest enclosing circle lies completely on the disk, is $2/3$.

Without loss of generality, assume that the perimeter of the disk is $x^2+y^2=1$, and the two points are $(x,y)$ and $(0,\sqrt t)$ where $t$ is uniformly distributed in $[0,1]$.

The smallest enclosing circle has centre $C\left(\frac{x}{2}, \frac{y+\sqrt t}{2}\right)$ and radius $r=\frac12\sqrt{x^2+(y-\sqrt t)^2}$. If the smallest enclosing circle lies completely on the disk, then $C$ lies within $1-r$ of the origin. That is,

$$\sqrt{\left(\frac{x}{2}\right)^2+\left(\frac{y+\sqrt t}{2}\right)^2}\le 1-\frac12\sqrt{x^2+(y-\sqrt t)^2}$$

which is equivalent to

$$\frac{x^2}{1-t}+y^2\le1$$

The area of this region is $\pi\sqrt{1-t}$, and the area of the disk is $\pi$, so the probability that the smallest enclosing circle lies completely on the disk is $\sqrt{1-t}$.

Integrating from $t=0$ to $t=1$, the probability is $\int_0^1 \sqrt{1-t}dt=2/3$.

Edit

From the comments, @Varun Vejalla has run trials that suggest that, for small values of $n$, the probability (that the enclosing circle lies completely on the disk) is $\frac{n}{2n-1}$, and that the limiting probability is $\frac12$. There should be a way to prove these results.

Edit2

I seek to generalize this question here.

$\endgroup$
14
  • 3
    $\begingroup$ intuition is simple: an infinite number of points selected with uniform probability will eventually "fill in" the entire disk. In that case, the smallest enclosing circle will be the disk itself. So, the probability that the smallest enclosing ciricle will be the disk itself is $1$ as $n \to \infty$. $\endgroup$ Nov 4, 2023 at 3:44
  • 2
    $\begingroup$ Quote: "The probability that the smallest enclosing circle will be the disk itself is $1$ as $n\to\infty$." Using the formal definition of limit, this implies that there exists $N$ such that for all $n>N$, the probability that the enclosing circle "will be the disk itself" is greater than $0.99$. But for all values of $n$ , the probability that the enclosing circle "will be the disk itself", is $0$. $\endgroup$
    – Dan
    Nov 4, 2023 at 4:34
  • 1
    $\begingroup$ Here's my intuition for it being 1. For any $n$, the smallest circle is either defined by two points (which would be a diameter) or three points on the edge. As $n\to\infty$, I think the three-points case dominates. Then as $n\to\infty$, these three points will all be near the edge of the disk and they will make an acute triangle. Then I think this means the circumcircle will be contained within the disk (with probability approaching $1$ as the points get closer to the edge of the disk). $\endgroup$ Nov 4, 2023 at 4:59
  • 3
    $\begingroup$ @RyRytheFlyGuy The smallest circle contains at least $2$ of the points chosen (on the circle itself), and this event for any particular circle has measure $0$ (indeed, positive codimension in the appropriate configuration space). $\endgroup$
    – coiso
    Nov 4, 2023 at 5:07
  • 1
    $\begingroup$ I wasn't able to test for very high values since the algorithm for getting the smallest circle is slow (and I'm using Python), but with n=1,000, out of 10,000 trials, in 5,028 of those, the smallest circle lies within the disk. After seeing that, I'm tempted to say the probability is 0.5. What I said earlier about the three-points case dominating still seems to hold though. $\endgroup$ Nov 7, 2023 at 21:30

2 Answers 2

16
+100
$\begingroup$

First, let me state two lemmas that demand tedious computations. Let $B(x, r)$ denote the circle centered at $x$ with radius $r$.

Lemma 1: Let $B(x,r)$ be a circle contained in $B(0, 1)$. Suppose we sample two points $p_1, p_2$ inside $B(0, 1)$, and $B(x', r')$ is the circle with $p_1p_2$ as diameter. Then we have $$\mathbb{P}(x' \in x + dx, r' \in r + dr) = \frac{8}{\pi} r dxdr.$$

Lemma 2: Let $B(x,r)$ be a circle contained in $B(0, 1)$. Suppose we sample three points $p_1, p_2, p_3$ inside $B(0, 1)$, and $B(x', r')$ is the circumcircle of $p_1p_2p_3$. Then we have $$\mathbb{P}(x' \in x + dx, r' \in r + dr) = \frac{24}{\pi} r^3 dxdr.$$ Furthermore, conditioned on this happening, the probability that $p_1p_2p_3$ is acute is exactly $1/2$.

Given these two lemmas, let's see how to compute the probability in question. Let $p_1, \cdots, p_n$ be the $n$ points we selected, and $C$ is the smallest circle containing them. For each $i < j < k$, let $C_{ijk}$ denote the circumcircle of three points $p_i, p_j, p_k$. For each $i < j$, let $D_{ij}$ denote the circle with diameter $p_i, p_j$. Let $E$ denote the event that $C$ is contained in $B(0, 1)$.

First, a geometric statement.

Claim: Suppose no four of $p_i$ are concyclic, which happens with probability $1$. Then exactly one of the following scenarios happen.

  1. There exists unique $1 \leq i < j < k \leq n$ such that $p_i, p_j, p_k$ form an acute triangle and $C_{ijk}$ contains all the points $p_1, \cdots, p_n$. In this case, $C = C_{ijk}$.

  2. There exists unique $1 \leq i < j \leq n$ such that $D_{ij}$ contains all the points $p_1, \cdots, p_n$. In this case, $C = D_{ij}$.

Proof: This is not hard to show, and is listed on wikipedia.

Let $E_1$ be the event that $E$ happens and we are in scenario $1$. Let $E_2$ be the event that $E$ happens and we are in scenario $2$.

We first compute the probability that $E_1$ happens. It is $$\mathbb{P}(E_1) = \sum_{1 \leq i < j < k \leq n} \mathbb{P}(\forall \ell \neq i,j,k, p_\ell \in C_{ijk} , C_{ijk} \subset B(0, 1), p_ip_jp_k \text{acute}).$$ Conditioned on $C_{ijk} = B(x, r)$, Lemma 2 shows that this happens with probability $\frac{1}{2}r^{2(n - 3)} \mathbb{1}_{|x| + r \leq 1}$. Lemma 2 also tells us the distribution of $(x, r)$. Integrating over $(x, r)$, we conclude that $$\mathbb{P}(\forall \ell \neq i,j,k, p_\ell \in C_{ijk} , C_{ijk} \subset B(0, 1), p_ip_jp_k \text{acute}) = \int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 3)} \cdot \frac{12}{\pi} r^3 dr dx.$$ Thus we have $$\mathbb{P}(E_1) = \binom{n}{3}\int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 3)} \cdot \frac{12}{\pi} r^3 dr dx.$$ We can first integrate the $x$-variable to get $$\int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 3)} \cdot \frac{12}{\pi} r^3dr dx = 12 \int_0^1 r^{2n - 3}(1 - r)^2 dr.$$ Note that $$\int_0^1 r^{2n - 3}(1 - r)^2 dr = \frac{(2n - 3)! * 2!}{(2n)!} = \frac{2}{2n * (2n - 1) * (2n - 2)}.$$ So we conclude that $$\mathbb{P}(E_1) = \frac{n - 2}{2n - 1}.$$ We next compute the probability that $E_2$ happens. It is $$\mathbb{P}(E_2) = \sum_{1 \leq i < j \leq n} \mathbb{P}(\forall \ell \neq i,j, p_\ell \in D_{ij} , D_{ij} \subset B(0, 1)).$$ Conditioned on $D_{ij} = B(x, r)$, this happens with probability $r^{2(n - 2)} \mathbb{1}_{|x| + r \leq 1}$. Lemma 1 tells us the distribution of $(x, r)$. So we conclude that the probability that $$\mathbb{P}(\forall \ell \neq i,j, p_\ell \in D_{ij} , D_{ij} \subset B(0, 1)) = \int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 2)} \cdot \frac{8}{\pi} r dr dx.$$ So $$\mathbb{P}(E_2) = \binom{n}{2}\int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 2)} \cdot \frac{8}{\pi} r dr dx.$$ We compute that $$\int_{B(0, 1)}\int_0^{1 - |x|} r^{2(n - 2)} \cdot \frac{8}{\pi} r dr dx = 8\int_0^1 r^{2n - 3} (1 - r)^2 dr = 8 \frac{(2n - 3)! 2!}{(2n)!}.$$ So we conclude that $$\mathbb{P}(E_2) = 8 \binom{n}{2} \frac{(2n - 3)! 2!}{(2n)!} = \frac{2}{2n - 1}.$$ Finally, we get $$\mathbb{P}(E) = \mathbb{P}(E_1) + \mathbb{P}(E_2) = \boxed{\frac{n}{2n - 1}}.$$ The proofs of the two lemmas are really not very interesting. The main tricks are some coordinate changes. Let's look at Lemma 1 for example. The trick is to make the coordinate change $p_1 = x + r (\cos \theta, \sin \theta), p_2 = x + r (-\cos \theta, -\sin \theta)$. One can compute the Jacobian of the coordinate change as something like $$J = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \cos \theta & \sin \theta & -\cos \theta & -\sin \theta \\ -r\sin \theta & r\cos \theta & r\sin \theta & -r\cos \theta \\ \end{bmatrix}.$$ And we can compute that $|\det J| = 4r$. As $p_1, p_2$ has density function $\frac{1}{\pi^2} \mathbf{1}_{p_1, p_2 \in B(0, 1)}$, the new coordinate system $(x, r, \theta)$ has density function $$\frac{4r}{\pi^2} \mathbf{1}_{p_1, p_2 \in B(0, 1)}$$ The second term can be dropped as it is always $1$ in the neighbor of $(x, r)$. To get the density of $(x, r)$ you can integrate in the $\theta$ variable to conclude that the density of $(x, r)$ is $$\frac{8r}{\pi}$$ as desired.

The proof of Lemma 2 is analogous, except you can use the more complicated coordinate change from $(p_1, p_2, p_3)$ to $(x, r, \theta_1, \theta_2, \theta_3)$ $$p_1 = x + r (\cos \theta_1, \sin \theta_1), p_2 = x + r (\cos \theta_2, \sin \theta_2), p_3 = x + r (\cos \theta_3, \sin \theta_3).$$ The Jacobian $J$ is now $6$ dimensional, and Mathematica tells me that its determinant is $$|\det J| = r^3|\sin(\theta_1 - \theta_2) + \sin(\theta_2 - \theta_3) + \sin(\theta_3 - \theta_1)|.$$ So we just need to integrate this in $\theta_{1,2,3}$! Unfortunately, Mathematica failed to do this integration, but I imagine you can do this by hand and get the desired Lemma.

$\endgroup$
3
  • 1
    $\begingroup$ The TBD outline: Choose any $p_i$ on the convex hull. There's a line through $p_i$ with all other points on the same side of that line. With a radius perpendicular to that line and long enough, a circle through $p_i$ can enclose all points. At some minimum radius, circle $C_2$ also goes through some unique $p_j$. Parameterize the set of circles through $p_i$ and $p_j$ in a continuous way. As we shrink from $C_2$ to $D_{ij}$, either there is some minimum radius where the circle goes through a unique $p_k$, with triangle $p_i p_j p_k$ acute, or else $D_{ij}$ contains all the points. $\endgroup$
    – aschepler
    Nov 8, 2023 at 18:34
  • $\begingroup$ How exactly do you sample the points on the disc? With a rejection sampling? If not, do you sample radius and angle? $\endgroup$ Nov 16, 2023 at 10:03
  • 2
    $\begingroup$ I don't think the algorithmic procedure is important for this particular problem, but if you want you could reject sample (say sample uniformly from [0, 1]^2 and reject if the point lies outside the unit circle.) $\endgroup$
    – abacaba
    Nov 16, 2023 at 16:59
-1
$\begingroup$

Intuitive answer:

Let $R_d$ be the radius of the disk and let $R_e$ be the radius of the enclosing circle of the random points on the disk and $R_p$ be the radius of a circle that passes through the outermost points such that all selected random points on the disk either lie on or within $R_p$.

The answer to this question is highly dependent on the exact precise definitions of the terms and phrases used in the question.

Assumption 1: Does the definition of "enclosing disk ...(of the points)... lies completely on the disk" includes the case of the enclosing circle lying exactly on the perimeter of the disk? i.e does it mean $R_e < R_d$ or $R\leq R_d$? I will assume the latter.

Assumption 2: Does the smallest enclosing circle of the points include the case of some of the enclosed points lying on the enclosing disk? i.e. does it mean $R_e > R_p$ or $R_e = R_p$? I will assume the latter.

It is well known that a circle can be defined by a minimum of 3 non colinear points. The question can now be boiled down to "If there are infinitely points on the disk, what is the probability of at least 3 of the points being on the perimeter of the disk?"

Intuition says that if there are an infinite number of points that are either on or within the perimeter of the disk, then the probability of there being 3 points exactly on the perimeter of the disk is exactly unity. If there are at least 3 points exactly on the perimeter of the disk then the enclosing circle lies completely on the disk, so the answer to the OP question is:

"The probability that the smallest circle enclosing $n$ random points on a disk lies completely on the disk, as $n\to\infty$, is 1.

If we define the meaning of "enclosing circle lies completely on the disk" to mean strictly $R_e < R_d$ then things get more complicated. Now the question boils down to "What is the probability of an infinite number of random points on the disk not having any points exactly on the perimeter of the disk?"

If any of the random points lie exactly on the perimeter of the disk, then the enclosing circle touches the perimeter of the disk and by the definitions of this alternative interpretation of the question, the enclosing circle does not lie entirely within the perimeter of the disk. The intuitive probability of placing an infinite number of random points on the disk without any of the points landing exactly on the perimeter of the disk is zero, so the answer to this alternative interpretation of the question is:

"The probability that the smallest circle enclosing $n$ random points on a disk lies completely on the disk, as $n\to\infty$ = 0.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .