19
$\begingroup$

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?

$\endgroup$
1

6 Answers 6

15
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Do you know, if there is a generalization \ variation to this problem? For example not looking at planes, but arbitrary surfaces (tori for example).. or k-dimensional spheres, instead of mere circles... l-dimensional objects instead of points? $\endgroup$
    – Imago
    Feb 17, 2016 at 13:50
  • $\begingroup$ @David Why you know we can choose a B like that. $\endgroup$ Feb 17, 2016 at 13:54
  • $\begingroup$ @Imago The same argument works using $(n-1)$-dimensional spheres in $n$-dimensional space. $\endgroup$
    – David
    Feb 17, 2016 at 13:55
  • $\begingroup$ @MạnhNguyênNguyễnHoàng I've edited the question to prove that fact. $\endgroup$
    – David
    Feb 17, 2016 at 13:58
  • 1
    $\begingroup$ @MạnhNguyênNguyễnHoàng I have given what I consider a proof. If you are more specific about which statements are insufficiently justified in your view, I can try to respond. $\endgroup$
    – David
    Feb 17, 2016 at 14:06
14
$\begingroup$

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.

enter image description here


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.

$\endgroup$
5
  • 3
    $\begingroup$ As written, your first construction isn't guaranteed to work: it's possible for the center of the initial circle to be on the same side of the line as the point you want to exclude, in which case continuously increasing the radius while keeping the same intersections will eventually give you a circle containing only the point to be excluded. $\endgroup$ Feb 17, 2016 at 16:33
  • $\begingroup$ @IlmariKaronen: very well observed. I have lazily rephrased. $\endgroup$
    – user65203
    Feb 17, 2016 at 17:52
  • $\begingroup$ That's an improvement. Although, given that the required change in the radius may not be monotone (and that, if it isn't, there's a point where you can increase the radius in two different ways), you might want to phrase it something like "move the center of the circle perpendicular to the line, while adjusting the radius to keep the points where the circle intersects the line fixed, until..." That should at least not be ambiguous, especially if you further point out that the center should be moved towards the side of the line that the single point lies on. :) $\endgroup$ Feb 17, 2016 at 23:38
  • $\begingroup$ @IlmariKaronen: "the required change in the radius may not be monotone ". Actually there is no need to continuously adjust the radius, jumping to the final value is enough. $\endgroup$
    – user65203
    Feb 18, 2016 at 7:02
  • 1
    $\begingroup$ Sure, but that's how you're asking people to visualize it. And the issue still remains that, for every (sufficiently large) final radius and pair of intersection points, there are two distinct circles with that radius and intersections, only one of which can be a solution. (And yes, I realize that this is getting rather nitpicky; at this point, everyone's surely realized what you mean by "adjust the radius", if they're going to get it at all. I just feel that your answer, as nice as it already is, could be still better if that part was made a bit more explicit.) $\endgroup$ Feb 18, 2016 at 13:38
6
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ (+1) Super nitpicky comment but in "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" should acute be changed to "non-obtuse"? I think the triangle could be acute or right-angled, can't it? $\endgroup$
    – Silverfish
    Oct 28, 2023 at 11:57
  • $\begingroup$ @Silverfish: If a right-angled triangle is inscribed, the hypotenuse is a diameter of the circle. $\endgroup$
    – hardmath
    Oct 28, 2023 at 16:26
  • $\begingroup$ I know - I just read what you wrote as suggesting "if there are two points on the circumference, they form a diameter, and if there are three points, they form an acute triangle", which isn't quite right. I now see you didn't intend it to be read like that, but if you re-read it I think you'll see why I took it that way at first! It's hard to phrase clearly, I think this is why Wikipedia calls it a "not obtuse" triangle. How about something like: "... if we can find among those points lying on the boundary either two that form a diameter or three that form an acute triangle"? $\endgroup$
    – Silverfish
    Oct 28, 2023 at 18:20
  • $\begingroup$ Perhaps I'm characterizing something a little different from what the Wikipedia article is. In fact the bounding circle might have only two of the encircled points on it. That would be one case, where my characterization of the circle's diameter applies. If that diameter were accompanied by additional points on the bounding circle, then we would have one or more right triangles inscribed. But in general we cannot show that either an acute triangle is inscribed or a right triangle is inscribed in the bounding circle. $\endgroup$
    – hardmath
    Oct 28, 2023 at 21:09
  • $\begingroup$ Yes, though if a covering circle contains exactly 3 points from the set, it's minimal iff they form a non-obtuse triangle (probably the situation where the "non-obtuse" formulation is "nicest"). I think you and WP are expressing the same idea; maybe WP emphasises more that if you can find either 2 points forming a diameter or 3 forming a non-obtuse triangle, those points determined the minimal circle (for non-obtuse triangles, the circumcircle is the unique minimum covering circle, so those 3 points show you can't beat the circle you've drawn... $\endgroup$
    – Silverfish
    Oct 29, 2023 at 0:14
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.


This works for almost all center points, but if you happen to pick a point for which $r_1=r_2$ then just move it a sufficiently small step straight away from one of the points which are the same distance away.

$\endgroup$
1
0
$\begingroup$

Apologies for self-promotion but I believe it might be of interest to the OP. One can generalise this statement as follows.

Let $B$ be a closed, convex and symmetric around the origin subset of $\mathbb{R}^n$ with non-empty interior and whose boundary does not contain any line segments. Suppose that you have a finite set $F\subset \mathbb{R}^n$. Then for each $k<|F|$ there exists a homotetic image of $B$ that contains exactly $k$ points of $F$.

This is a consequence of Corollary 2 in this paper.

$\endgroup$

You must log in to answer this question.

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