4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Ricardo Andrade
    Commented Apr 10, 2014 at 13:26
  • $\begingroup$ Sorry for the confusion. I actually mean "disk". I changed the statement of the question. $\endgroup$
    – XiMS
    Commented Apr 11, 2014 at 4:22
  • $\begingroup$ I think the answer is given by Lev Soukhanov. See the post below. $\endgroup$
    – XiMS
    Commented Apr 11, 2014 at 4:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – XiMS
    Commented Apr 11, 2014 at 5:34

2 Answers 2

Reset to default
12
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

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