Take the 2-minute tour ×

Consider any n points on the circumference of a circle. Draw a straight line link between each pair of points with a link weight consisting of the cosine of the angle the link subtends at the centre.

It seems that If the convex hull of the point set contains the centre of the circle, then some point has the property that the sum of the link weights that meet that point are less than or equal to -1.

I have verified for the cases n=3 or 4 nodes and for many simulations - but cannot prove in general. Would be glad of any help

share|improve this question
What do you mean by a "link weight"? –  Yemon Choi Aug 18 '10 at 6:16
Another way to say it is that if a point is at (1, 0) then its link weights are the x values of the other points. –  Dan Brumleve Aug 18 '10 at 6:20
@Yemon, I take it Richard is just assigning a number to each chord (namely, the cosine of the angle subtended by the chord) and then asking whether there must be a point such that the sum of the numbers assigned to the chords meeting at that point is at most minus one. Richard chooses to call that number a link weight, but a rose by any other name.... –  Gerry Myerson Aug 18 '10 at 6:23

4 Answers 4

Center the circle at the origin. Consider the sum of all the points. If it is (0,0) then the statement is true for all points. Otherwise there is an arc of pi in which the sum has an x value less than 0. Since the condition of the convex hull enclosing (0,0) is equivalent to no two adjacent points being separated by more than pi, we are done (by the pigeonhole principle).

share|improve this answer

Assume $\sum_{i=1}^n a_i x_i=0$ with $x_i$ on the circle and $a_i>0$, $\sum a_i=1$. Then $\sum_{i=1}^n\sum_{j=1}^n a_i\langle x_i,x_j\rangle=0$.

It follows that for some $i$, $\sum_{j=1}^n\langle x_i,x_j\rangle\le 0$.

Since $\langle x_i,x_i\rangle=1$, it implies $\sum_{j; j\not=i} \langle x_i,x_j\rangle\le -1$ which is what you want.

share|improve this answer
By the circle above I meant the unit circle (so $\langle x, y\rangle$ is the cosine of the angle between $x$ and $y$. BTW, this works in any dimension just replace the unit circle with the unit sphere. –  Gideon Schechtman Aug 18 '10 at 11:54

This solution isn't much different at bottom from those of GS and DB but it's how I think of it. Let the circle be the unit circle in the complex plane. Let the points be $z_1,\dots,z_n$. The "link weight" of the chord joining $z_j$ to $z_k$ is the real part of $\overline{z}_jz_k$ (I omit the small amount of calculation needed to verify this). Let $S$ be the sum of all the $z_j$. Then the sum of the link weights at $z_j$ is the sum on all $k$ other than $j$ of the real part of $\overline{z}_jz_k$, which is the real part of ($\overline{z}_j$ times the sum of the $z_k$), which is ${\rm Re}(\overline{z}_j(S-z_j))={\rm Re}(\overline{z}_jS)-1$. If $S=0$, we're done; the sum of the link weights at $z_j$ is $-1$. If $S\ne0$, then the $z$ such that the real part of $\overline{z}S$ is positive form an open half plane with the origin on the boundary. The points can't all be in that open half plane, since the origin is in their convex hull. So at least one of the points $z_j$ has real part of $\overline{z}_jS$ at most zero, and we win.

share|improve this answer

There seems to be some misunderstanding re the problem, which I posted. The differences in the x coordinates between points are not equal or proportional to the link weights since the chord lengths between points vary.

This seems to be a very tricky problem probably requiring variational methods or the like.

share|improve this answer
What don't you understand about the two valid solutions that have been posted? –  Robin Chapman Aug 18 '10 at 10:45
Please make this a comment on your question or, even better, edit the question itself to avoid any misunderstanding! –  Mariano Suárez-Alvarez Aug 18 '10 at 13:39
The difference in x coordinates is required to be the same as the cosine of the difference in angle only when one of the points is at (1,0) and the circle is centered and normalized. My answer describes rotating a candidate point into this position so the two definitions are the same in that case. –  Dan Brumleve Aug 19 '10 at 4:26
Richard, the other thing I might not have explained very well is that I am giving each point a link weight of 1 to itself. This way all you have to do is show that the sum is negative and it isn't even necessary to normalize the circle to a unit radius. –  Dan Brumleve Aug 19 '10 at 6:23

Your Answer


