Given n random points on a circle, find, with proof, the probability that the convex polygon formed by these points does not contain the center of the circle. at first i thought it easiest to find probability that the center IS enclosed and then take 1 minus that . the probability would be that at least 1 point lie on one side of the circle or the semi circle while n-1 points lie on the other . the case fir a triangle , n=3 would mean two of the points lie on the same semi circle and the third lies on another

  • $\begingroup$ I can't make this precise, but I believe that this might be related to the lonely runner conjecture en.wikipedia.org/wiki/Lonely_runner_conjecture . $\endgroup$ – Paul Frost Aug 31 '18 at 22:25
  • $\begingroup$ Not so simple, 2 points can lie within a semi circle with a 3rd point in the other semi circle which still doesn't contain the circle center. Take a look at this previous problem...... math.stackexchange.com/questions/2786367/…. $\endgroup$ – Phil H Aug 31 '18 at 22:40
  • $\begingroup$ @PhilH It's not true that all semicircles will contain all of the points but won't there be a partition of the circle in which all of the points are contained in the same semicircle? $\endgroup$ – John Douma Aug 31 '18 at 22:55
  • $\begingroup$ John Douma I was responding to the contributors comment "the case for a triangle , n=3 would mean two of the points lie on the same semi circle and the third lies on another" The whole problem is to determine the probability of all points being in a semicircle. With few points, that semicircle "can" be one of many, but the number can and will diminish as points are added and may even become zero. The difficulty with this problem is accounting for a diminishing sector or arc into which a point can be placed for all points to remain within a semi circle. $\endgroup$ – Phil H Sep 1 '18 at 1:43

The space of all possible configurations is $C^n$, where $C$ is the unit circle, here identified with the interval $J=[0,2\pi)$ via $J\to C$, $t\to P(t)=\cos t+i\sin t$.

Now fix such a "winning configuration" of points $$(A_1,\dots,A_n)=(P(t_1),\dots,P(t_n))\ ,$$ so that the center $0$ is not in the convex hull. Now reorder them in cyclic trigonometric order on the circle $C$. Add the $0$ as a new point and build the "bigger" convex hull. Then $0$ is one of the vertices in this bigger convex hull, has two adjacent vertices, uniquely determined, $A_j$ and $A_k$, $1\le j,k\le n$, and exactly one of these two, denoted $A^*$, precedes the other one in the mentioned cyclic order. It is characterized by the fact that on the trigonometrical oriented arc segment $s(A^*)$ from the opposite of $A^*$ to $A^*$ we find all other points.

So to realize a "winning configuration" we have to make the choice of one index $j$, make an arbitrary choice of $A^j$ (which becomes $A^*$ in a second=, then choose arbitrarily the other $(n-1)$ points in the semicircle $s(A_j)$, so that for this configuration $A_j=A^*$. So and only so we can realize a "winning configuration". The corresponding probability is thus $$ \frac{n\cdot(2\pi)\cdot \pi^{n-1}}{(2\pi)^n} = \frac n{2^{n-1}}\ . $$


Note: This seems to be a "high probability" for $n=3$ from our "feeling" of choosing a triangle and a circle around. Let us use some other argument for this special case. (Well, we take the "circle around" first, then three points on it.)

Because of the circular symmetry, we fix the first point $A_1=1+0i$ on the unit circle in $\Bbb C$. A second arbitrary point $A_2$ on $C$ has either positive or negative imaginary part, we split in two cases, "upper" and "lower" semicircle. Where can we take $A_3$ now so that $A_1A_2A_3$ does not cover (in the convex hull) the origin $0$?

  • one possible choice of $A_3$ is in the "upper" semicircle if $A_2$ is there, this happens with probability $1/4$,

  • one other possible choice of $A_3$ is in the "lower" semicircle if $A_2$ is there, this happens again with probability $1/4$,

  • and one final chance is to take $A_3$ in the semicircle from $A_2$ containing $A_1$, so that among the points $A_2,A_3$ one is "lower", and one is "upper", so we are integrating w.r.t. $A_2$ in the "upper" semicircle, i.e. $t_2\in [0,\pi)$, the length of the corresponding interval for $t_3$, which is $(t_2-\pi,0]$. (Same by symmetry w.r.t. the real axis, or w.r.t. $A_2\leftrightarrow A_3$ if $A_2$ is "lower".) The graph of the map $t_2\to (\pi-t_2)$ (associating the above length) is simple... The contribution to the wanted probability from this case is again $1/4$.


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.