Circle enclosing all but one of $n$ points

It looks like a simple question but it turns out rather difficult to me. Here is the question:

Given $n$ points on the plane, can we always draw a circle that includes exactly $n-1$ of them?

Solution 1:

Yes. Let $A_1, \dots, A_n$ be the points. Pick a point $B$ in the plane that is not on the perpendicular bisector of any of the (finitely many) segments $A_i A_j$. Let $c_i = BA_i$ for $i = 1, \dots, n$. Because of the way $B$ was selected, we have $c_i \ne c_j$ for $i \ne j$. After reordering $A_1, \dots, A_n$ if necessary, we may assume $c_1 < c_2 < \dots < c_n$. Let $r \in (c_{n-1},c_n)$ and draw the circle with centre $B$ and radius $r$.

Edit In response to a comment, I will prove that given a finite number of lines $l_1, \dots, l_s$, there exists a point $B$ not belonging to any of them.

Draw any line $m$ whose slope is not the same as that of any of the lines $l_1, \dots, l_s$. Then $m$ has only finitely many intersections with those lines. Pick a point on $m$ other than the intersections.

Solution 2:

Unless some points overlap, you can draw a straight line that leaves a single point apart (and not through it).

Then draw any circle that encloses the other $n-1$ points.

If it doesn't enclose the single point, you are done.

Otherwise, adjust the circle radius while keeping the same two intersections, until the single point is left outside.

Constructively:

Compute the convex hull and take out one extreme vertex. Update the hull. Find an edge such that its supporting line leaves the vertex out. Construct the minimum enclosing circle. A solution is the circle through the two intersection points between the supporting line and the enclosing circle, and the point on the bisector of these intersections at half distance to the vertex.

Solution 3:

The problem can be easily solved using the minimum bounding circle and its properties.

Since there are only finitely many (distinct) points, it is certainly possible to include all of them in a circle. Shrinking the circle as much as possible produces a unique smallest circle that bounds the points, and at least two of the points will lie on the boundary of that circle. [In fact the minimum bounding circle is characterized either by having two points which form a diameter of the circle, or three points on the boundary that form an acute triangle.]

All we need is for one point to lie on the boundary of the circle containing all of them, because we can then draw a short chord on the circle which separates that point from the rest of the points.

A very big circle can then be drawn which approximates the line extending that chord, approximates it closely enough that one point remains outside and the other points are within it.

Solution 4:

HINT

The point you want to keep outside should have a relation to the envelope of the rest of the points.

For example if the $n{th}$ point is the center of $n-1$ points on the rim of a circle then it is impossible to draw such a circle.

The excluded point for example should not be inside any triangle made by combinations of three points taken at a time from rest of $n-1$ points.

Solution 5:

Choose any center point $p_{\mathrm{ctr}}$. Let $r_1>r_2$ the two largest^† distances between $p_{\mathrm{ctr}}$ and the individual points. Then $$ r = \frac{r_1+r_2}2 $$ is a radius around $p_{\mathrm{ctr}}$ which excludes exactly one point (the one with $r_1$) from the circle.