Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a question, but not sure how to prove this.

We are given $n$ points in the Euclidean plane such that there exists no disk of radius $a$ which contains all of the points.

Conjecture: There must exist three of these points which are not contained in a disk of radius $a$.

Any idea about how to prove this?

Thanks.

share|improve this question

closed as off-topic by alvarezpaiva, Stefan Kohl, Andrey Rekalo, Ryan Budney, David Roberts Apr 16 at 1:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – alvarezpaiva, Stefan Kohl, Andrey Rekalo, Ryan Budney, David Roberts
If this question can be reworded to fit the rules in the help center, please edit the question.

    
When you say that points are contained in a circle, do you mean that the points lie on the circle or that the points are within the closed disc bounded by the circle? –  Ricardo Andrade Apr 10 at 13:26
    
Sorry for the confusion. I actually mean "disk". I changed the statement of the question. –  XiMS Apr 11 at 4:22
    
I think the answer is given by Lev Soukhanov. See the post below. –  XiMS Apr 11 at 4:50
1  
Thanks! A more concrete explanation can be found at cut-the-knot.org/pythagoras/ConvexSets/…. This can help us have a better understanding of Helly's theorem and its applications. –  XiMS Apr 11 at 5:34

2 Answers 2

up vote 11 down vote accepted

There is a classical result of convex geometry, called Helly's theorem (http://en.wikipedia.org/wiki/Helly%27s_theorem). It states that if you have $n$ convex subsets of $R^d$ and any $d+1$ of these convex subsets have nontrivial intersection, then all of them have nontrivial intersection.

For your question you just apply this theorem to the balls of radius $a$ around your points.

share|improve this answer
    
Thanks.This quite helpful. –  XiMS Apr 11 at 4:47

Start by choosing two of the points $A$ and $B$ such that all other points lie on the same side of the line $AB$. (This can be done by moving a line from the distance to the points until it meets a point, and then turning the line until you meet another point.) It there are other points on the line AB, you should choose $A$ and $B$ such that the other points lie between $A$ and $B$. Now consider circles through these two points with various radius where the larger part of the circle lies on the side of the other points. Then a circle with larger radius covers all the area of a circle of smaller radius (inside the half space where the points lie). Hence, the biggest circle you need to cover $A$, $B$ and a third point already covers all points.

So, $A$, $B$ and the third point for which one needed this biggest circle are the three points in your conjecture.

share|improve this answer

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