What is the chance that an $n$-gon whose vertices lie randomly on a circle's circumference covers a majority of the circle's area?

The vertices are chosen completely randomly and all lie on the circumference. Is there a formula for the chance that an $n$-gon covers over $50$% of the area of the circle, with any input $n$?

I tried to find something, however I did not know what to look for when I realized the first three values of $n$ would yield a $0$% chance (one point and two points are obviously $0$ because they don't cover any area, and I don't think any inscribed triangle can cover over $50$% of the circle's area). I also believe it to be over $50$% for $n=4$ because when I tried to randomly distribute the points I seemed to get mostly areas that covered most of the circle.

Note: The polygon should be a simple polygon, formed by connecting each point to the two points closest to it.

Solution 1:

This is a hard problem! I'll settle for showing that when $n=4$, $p\approx0.1264937239602$.

Let the vertices of any quadrilateral be at angles $0\leq \theta_1\leq\theta_2\leq\theta_2\leq\theta_4\leq 2\pi$. By symmetry, we can fix $\theta_1=0$ and $\theta_3\leq\pi$. So the quadrilateral has points at $p_1=(1,0)$, $p_2=(\cos\theta_2,\sin\theta_2)$, $p_3=(\cos\theta_3,\sin\theta_3)$ where $\sin\theta_3>0$, and $p_4=(\cos\theta_4,\sin\theta_4)$.

The area $A$ inside the quadrilateral is a function of its two diagonals, $\overline{p_1p_3}$ and $\overline{p_2p_4}$. Namely, it is $A=\frac12bh$ where the baseline is $b=p_1p_3=2\sin\frac{\theta_3}{2}$ and the height $h$ is the projection of $\overline{p_2p_4}$ orthogonal to $\overline{p_1p_3}$. We'll write a nice expression for $h$ later. For now, just observe that $h\leq 2$, so $A\leq b\leq2$.

Let $T$ be the threshold area we're interested in. In your statement of the problem, $T=\pi/2\approx1.55$. For the following to work, we just need $T$ between the areas of the inscribed regular triangle and square, $3\sqrt3/4\approx1.3$ and $2$.

We want to calculate $$p=\frac{\iiint_{A>T}d^3\theta}{\iiint d^3\theta}$$ where the bottom integral is taken over the entire allowed range of $\theta_2<\theta_3<\pi<\theta_4$. The denominator is $(2\pi)^3/(2\cdot 3!)$, so $$p=\frac{12}{(2\pi)^3}\int_0^\pi d\theta_3\iint[A>T] d\theta_2d\theta_4$$ where the Iverson bracket $[q]$ is $1$ where $q$ is true and $0$ where $q$ is false.

Now let's change variables: Let $t_2=\theta_2-\frac{\theta_3}{2}$ and similarly $t_4=\theta_4-\frac{\theta_3}{2}-\pi$. Then we have $h=\cos t_2 +\cos t_4$. (If this seems like a miracle, draw the right diagram.) And when $\theta_3$ is fixed, we have $d\theta_2=dt_2$ and $d\theta_4=dt_4$, so $$p=\frac{12}{(2\pi)^3}\int_0^\pi d\theta_3\iint[A>T] dt_2dt_4.$$

By this point you may be complaining about the bounds on $\theta_2$, $\theta_4$, $t_2$, and $t_4$, which I've largely glossed over. What if the ordering constraints $0<\theta_2<\theta_3<\theta_4<2\pi$ have some complex interaction with the constraint $A>T$? Well, the fact that $T$ is greater than the area of any inscribed triangle already guarantees that in the region $A>T$, the ordering constraints are easily satisfied. So we don't have to worry about them, and we can just integrate $t_2,t_4$ on any reasonable interval, say from $-\pi/2$ to $\pi/2$, regardless of the value of $\theta_3$!

Better yet, by symmetry, we can require $t_2>0$ and $t_4>0$ and multiply our integral by $4$ to compensate. And we can also take this opportunity to change the last variable: $t_3=\frac{\theta_3}{2}$, so $d\theta_3=2dt_3$. So now: $$p=\frac{96}{(2\pi)^3}\int_0^{\pi/2} dt_3\int_0^{\pi/2}dt_2\int_0^{\pi/2}dt_4\left[A=\frac12bh=(\sin t_3)(\cos t_2 +\cos t_4)>T\right]$$ That inequality on $t_2$ and $t_4$ isn't easy to integrate. Compare my question here: Area bounded by $\cos x+\cos y=1$. Instead, let's push ahead with brute force and solve for $t_4$: (remember that $0<t_4<\pi/2$) $$t_4<\cos^{-1}\left(\frac{T}{\sin t_3}-\cos t_2\right)$$ provided that this quantity exists in the real numbers, which requires $$\frac{T}{\sin t_3}-\cos t_2\leq1\implies t_2\leq\cos^{-1}\left(\frac{T}{\sin t_3}-1\right)$$ ...provided that that quantity exists in the real numbers, which requires $$\frac{T}{\sin t_3}-1\leq 1\iff 2\sin t_3\geq T $$ ...which makes sense, it's just a consequence of $b\geq A\geq T$. So: $$p=\frac{12}{\pi^3}\int_{\sin^{-1}(T/2)}^{\pi/2} dt_3\int_0^{\cos^{-1}\left(T/\sin t_3-1\right)}dt_2\cos^{-1}\left(\frac{T}{\sin t_3}-\cos t_2\right)$$

Now, the integrand has large derivatives near the upper limit of the $t_2$ integral, so we could make this a little easier by dividing out another symmetry and requiring $t_2<t_4$. But as it turns out, this integral is already easy enough for scipy to approximate quickly and precisely:

>>> scipy.integrate.dblquad(
...     func=lambda t2,t3: 12/(pi**3) * acos(T/sin(t3)-cos(t2)),
...     a=asin(T/2),
...     b=pi/2,
...     gfun=lambda t3: 0,
...     hfun=lambda t3: acos(T/sin(t3)-1)  )
(0.12649372396022962, 1.4043624481122576e-15)

This is consistent with the first few digits $0.12647\pm0.00004$ that I got from random sampling, so I'm pretty sure that it's right.

The digits $0.1264937239602$ don't appear in the Inverse Symbolic Calculator, OEIS, or Google. I also tried a rational value $T=1.5$, hoping to get a nicer value, but I got $p_{T=1.5}\approx0.162088738800$, which is similarly obscure. This suggests to me that there is no nice formula for $p$, even in the single case $n=4$, let alone for other $n$.

(But maybe someone better at evaluating hairy definite integrals can work their magic...?)

The other thing you might want to investigate is the asymptotic behavior for large $n$. Even if there isn't a nice formula for each $p_n$, there might still be a nice formula like "$p_n=1-42n^{-2}+O(e^{-n})$". (That's a phony formula; I don't know the real thing!)