2

Could You help me give a proof that:

Given a finite number $(>3)$ of points in the Euclidean plane, then exist a circle through three points such that any other points inside (or lie on) the circle.

enter image description here

Walt van Amstel
  • 925
Cố Gắng Lên
  • 333
  • 1
    You would obviously need to assume that the points do not all lie on a straight line – Walt van Amstel Jun 08 '17 at 14:22
  • 1
    Two ideas that I don't know how to make rigorous. (1)Start with a circle that contains all the points and keep shrinking it down and show that it will stop only when there's three points in the set. (2) Consider all circles through each set of three points in the convex Hull and show that one of them will contain all the points. – marty cohen Jun 08 '17 at 14:35
  • Thank to You, maybe is this an aswer? – Cố Gắng Lên Jun 08 '17 at 14:40
  • have a look to (https://en.wikipedia.org/wiki/Smallest-circle_problem). – Jean Marie Jun 08 '17 at 15:47
  • @Jean Marie: The minimum bounding circle doesn't necessarily pass through 3 of the points. – Jens Jun 08 '17 at 15:52
  • @Jens you are right, it is a more general issue. – Jean Marie Jun 08 '17 at 15:54
  • @martycohen I don't have the intuition to make your second idea rigorous, but for the first it can go like this: pick any position for a center $c$, take the smallest ball centered at $c$ containing all points. If this ball go through only one point $x_1$, move $c$ toward $c_1$. At some point, you can't move $c$ closer without losing some point, you can prove the ball goes through another point $x_2$. Now move $c$ along the mediator of segment $x_1x_2$, you get a third point. – N.Bach Jun 08 '17 at 16:03

1 Answers1

2

Start with the convex hull of the points. Pick any edge of that hull, and extend it to a line. That line can be seen as a degenerate circle of infinite radius, or more usefully of curvature zero. Now start increasing the curvature while maintaining contact with the two incident points. These two points and the curvature uniquely define the circle, which makes this easy to describe. There are two possible scenarios. Either you at some point encounter a curvature for which the circle starts touching another point from your set. In that case you are done.

Or you increase the curvature as much as you can without encountering that situation. In that case you end up with a circle which has the two points antipodal on a diameter, and all the other points within. Which means that by coincidence you picked points which are particularly far apart, farther than any other pair of points in your set (since two points inside the circle have to be less than the diameter away from one another). Start over with a different edge from the convex hull and you are good.

There are some special cases worth considering. It might happen that you already touch a thrid point in the initial configuration, with curvature zero. That can happen if you have collinear points on your convex hull. If you pick the outermost points from such a collinear edge, you do touch the inner points initially, but move away from them as the curvature increases.

If all your points are in a straight line, then choosing the outermost points of each collinear edge leaves you with exactly one pair to choose. You will end up in the position where the circle of maximal curvature still only touches two points, and you won't have a different edge to choose from. So in that case the statement holds only if you also allow circles of zero curvature.

See also A circle with infinite radius is a line.

MvG
  • 42,596
  • What if, when you increase the curvature, you encounter not one but two points at the same time? Then that circle fails to witness the desired statement. (Indeed, the desired statement is false if the points are the edges of a cyclic polygon - but no such exception is made here) – Milo Brandt Jun 08 '17 at 21:28
  • @MiloBrandt: The original statements requires all other points to lie inside or on the circle, so having more than three points incident with the circle is permissible. Probably should have made that more clear, but I considered the other special cases more interesting. – MvG Jun 08 '17 at 21:30
  • Ah, I misread the question. Then I see that this works. – Milo Brandt Jun 08 '17 at 21:35