Separating point sets with a circle: a rigorous proof from Interactive Mathematics Miscellany and Puzzles

Separating point sets with a circle

Lemma 1

If S is a bounded set of points in the plane then there is a smallest closed disk that contains S.

Proof

Since S is bounded, there is a disk of radius d that contains S. The set of disks of radius d or less that contain S is compact, so there is a smallest one.

Lemma 2

If S is any set of points in the plane there is at most one smallest closed disk that contains them.

Proof

Consider two disks of radius r with distance 2d between their centers. There is a disk of radius sqrt(r² - d²) that contains their intersection.

Lemma 3

If S is a finite set of points in the plane then the unique smallest closed disk that contains S either has two points of S as endpoints of a diameter or has three points of S on its boundary.

Proof

Let D be the unique smallest disk that contains S. If its boundary contains no points of S then translate it until its boundary contains one (or more). Rotate it around that point until its boundary contains two points of S (or more). Move its center closer to the line segment joining those points until either its center is on that segment or else there are three points of S on its boundary (or more).

Theorem

Let S be a finite set of points in the plane such that no 4 points in S are cocyclic. Let D be a smallest closed disk that contains at least n points of S (such a D exists because there are finitely many n-element subsets to try). Then D contains exactly n points of S.

Proof

Let D contain exactly points of S. For the sake of contradiction, assume m > n. Let D intersection S = T. Then D is the smallest closed disk containing T. If two points of T are endpoints of a diameter of D then let P be one of those points, otherwise let P be any point in T that is also in the boundary of D. Let D' be the smallest closed disk containing T-P. If P is in D', then D' is a smallest closed disk containing T, so D = D'. Since no 4 points in S are cocyclic, the boundary of D' contains at most two points of T-P and those two points are not endpoints of a diameter, contradicting Lemma 3. Thus P is not in D', so D' contains exactly m-1 points of S. D' is smaller than D, or or else D is a smallest closed disk containing T-P, but there can be only one. Since m-1≥n, D wasn't really the smallest closed disk containing at least n points of S.

To solve your problem dilate D slightly, so that n points are inside and n points are outside.

71537593