2
$\begingroup$

Final Version:

Given a convex quadrilateral, then at least one of the two diagonals satisfy this: if a disk contains it, then it should contain one of the rest two vertices of the quadrilateral.

2nd Version:

Suppose we have four points in the plane in general position, call them $a,b,c,d$ and take the quadrilateral they form. Take any disk that contains the longest diagonal. Then, this disk will contain at least one of the point not on the longest diagonal.

Edit: Where my question comes from? Stating again a new version of the problem.

I need a result like this for a problem in Machine Learning. The problem comes down to this. Given a circle in the plane, the points inside it are marked as $+1$ and points outside it as $-1$. Take the family of all circles in the plane and consider four arbitrary points in the plane. I want to show that I can't achieve all the possible labellings for these points by using circles from my family -we say in such case that these points can't be shattered. To make this more clear, let me mention for example that if we have three points in the plane then obviously we can take all the $2^3$ possible labelings of the three points by taking a circle that contains all of them, none of them, exactly one of them (x3) and exactly two of them (x3). I know that in the case of four points we can't do so and I am trying to prove that. If the convex hull of the four points is a segment, then obviously these points can't be shattered -if they are ordered $a,b,c,d$ in the segment then the labelling $(1,-1,1,-1)$ can't be realised, since a circle that contains $a$ and $c$ will also contain $b$ as well. If the convex hull of the four points is a triangle, then again these points can't be shattered -if $a,b,c$ are the vertices of the triangle then the labelling $(1,1,1,-1)$ can't be realized. So we are left with the case that the convex hull is a quadrilateral. In this case, it should be that there exists a labelling that can't be realized. If our quadrilateral is $a,b,c,d$ then I can see that all of the labellings can be realised except for $(1,-1,1,-1)$ or $(-1,1,-1,1)$. I thought that it would be the case that the labelling that fails to be realised is the one with $1's$ at the longest diagonal, but that's not the case, as Raffaele's answer suggests.

It seems sufficient to prove the following: given a quadrilateral, then at least one of the two diagonals satisfy this: if a disk contains it, then it should contain one of the rest two vertices of the quadrilateral.

Is this now true?

First Version:

Suppose we have four points in the plane in general position, call them $a,b,c,d$. Also suppose that $a,b$ have the longest distance among these points. Take any disk that contains this segment. Then, this disk will contain at least one of $c,d$.

It seems obvious intuitively that this holds, but I failed to prove it rigorously. Any suggestion?

$\endgroup$
  • $\begingroup$ Can you show your attempt? $\endgroup$ – John Wayland Bales Nov 4 '17 at 21:48
  • 3
    $\begingroup$ This isn't true. Take $a = (-2, 0)$, $b = (2, 0)$, $c = (-1, -2)$ and $d = (1, -2)$. Then $ab$ is the longest segment between pairs of points, but any disk centred at the origin with radius $2 < r < \sqrt{5}$ does not contain either of $c$ or $d$. $\endgroup$ – B. Mehta Nov 4 '17 at 21:50
  • $\begingroup$ Actually, although I have drawn many figures and tried to figure out what would be a compelling argument, I don't have something specific to present. $\endgroup$ – perlman Nov 4 '17 at 21:50
  • $\begingroup$ @B.Mehta You are right. I rephrased my initial problem. What about now? $\endgroup$ – perlman Nov 4 '17 at 21:58
  • 1
    $\begingroup$ A background link for those who is interested: VC-dimension. $\endgroup$ – Alex Ravsky Nov 11 '17 at 1:29
2
$\begingroup$

Given a convex quadrilateral, then at least one of the two diagonals satisfy this: if a disk contains it, then it should contain one of the rest two vertices of the quadrilateral.

I am glad to give a happy end to this question story. The answer is positive. Indeed, denote the vertices of the quadrilateral (in cyclic order) by $A$, $B$, $C$, $D$. Assume that a disk contains a diagonal $AC$, but none of the vertices $B$ and $D$. Let $A’C’$ be a chord of the disk containing the side $AC$. Then $\angle ABC+\angle ADC\le \angle A’BC’+\angle A’DC’<\pi$. Similarly, if an other disk contains a diagonal $BD$, but none of the vertices $A$ and $C$ then $\angle BAD+\angle BCD <\pi$. But then

$$2\pi=\angle ABC+\angle ADC+\angle BAD+\angle BCD<2\pi,$$

a contradiction.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Alex Ravsky thanks a lot for the proof. Let me mention that I have seen in many notes discussing the VC dimension of the circles, the argument that corresponds to my second version in the op, which proved to be wrong! $\endgroup$ – perlman Nov 11 '17 at 5:07
  • $\begingroup$ Alex Ravksy I wanted to give the 50 points of the badge, but by accident, I gave them to the other answer. Can we change that? If not, I hope it's not a big issue. $\endgroup$ – perlman Nov 11 '17 at 20:11
  • $\begingroup$ @perlman OK, no problem, I am not greedy. :-) Anyway, I am happy that now I can tell my colleagues that I have answered a perlman’s question (see, Grigori Perelman). :-)) $\endgroup$ – Alex Ravsky Nov 12 '17 at 6:20
  • $\begingroup$ haha it comes actually from this Perlman youtube.com/watch?v=KpYUaRg0aDw $\endgroup$ – perlman Nov 12 '17 at 18:31
2
+50
$\begingroup$

It is not true either. I was trying to prove your statement, when I realized what you can see in the picture below

Where do your question come from? Maybe if you tell us more we can help you better

Hope this helps $$...$$

enter image description here

$\endgroup$
  • $\begingroup$ Thank you so much for your help. I gave the background of my question in the initial post and I also gave a new version that I hope now is true. $\endgroup$ – perlman Nov 5 '17 at 19:36

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.