4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean by a "link weight"? $\endgroup$
    – Yemon Choi
    Commented Aug 18, 2010 at 6:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Commented Aug 18, 2010 at 6:20
  • 2
    $\begingroup$ @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.... $\endgroup$
    – Gerry Myerson
    Commented Aug 18, 2010 at 6:23

4 Answers 4

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Gideon Schechtman
    Commented Aug 18, 2010 at 11:54
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ What don't you understand about the two valid solutions that have been posted? $\endgroup$
    – Robin Chapman
    Commented Aug 18, 2010 at 10:45
  • 2
    $\begingroup$ Please make this a comment on your question or, even better, edit the question itself to avoid any misunderstanding! $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Aug 18, 2010 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Commented Aug 19, 2010 at 4:26
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Commented Aug 19, 2010 at 6:23

You must log in to answer this question.

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