10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have edited to specify a simple polygon, so it should not intersect itself. $\endgroup$ – volcanrb Aug 9 '17 at 22:10
  • 1
    $\begingroup$ A related question and answer is here: math.stackexchange.com/questions/2362636/… $\endgroup$ – awkward Aug 9 '17 at 23:14
  • 3
    $\begingroup$ Suppose the edges of the polygon subtend angles $\theta_1,\dots,\theta_n$ at the origin. Then its area is $\frac12\sum\sin\theta_i$. For a random simple inscribed polygon, these angles are drawn uniformly from the simplex $\{(\theta_1,\dots,\theta_n):\theta_i\ge0,\sum\theta_i=2\pi\}$, and we want the probability that $\frac12\sum\sin\theta_i>\pi/2$. Not sure if this helps. $\endgroup$ – Rahul Aug 9 '17 at 23:34
  • $\begingroup$ I ran a quick experiment for $n=4$ and got over $\pi/2$ area on 1,263,910 out of 10,000,000 trials, for an estimate of $p=0.1264 \pm 0.0001$. But I could have made a mistake. $\endgroup$ – Chris Culter Aug 9 '17 at 23:38
  • $\begingroup$ More trials: $12647210/100000000 = 0.12647 \pm 0.00004$ $\endgroup$ – Chris Culter Aug 9 '17 at 23:51
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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