0
$\begingroup$

On a plane we have finite amount of points. Any three of them are not collinear. Show that there exist circle (formed with three or more points) that doesn't contain other points in it.

Source: a national mathematics magazine.

My approach:

Assume we have some circle created from 3 or more points. If in this circle (interior) exists some point, we take any two points from the border and one from the inside and create new circle.

And we can repeat it until we have circle without inner points.

Does this work?

  • 0
    @All: Thanks for the clarification. Indeed I did read it as lying "on" the circle.2012-11-13

3 Answers 3

3

Your argument is wrong. You assume that if $D$ is inside the circle circumscribing $ABC$ then one of the circles circumscribing $ABD$, $BCD$, or $ACD$ is inside the original circle. That is far from obvious, and actually false.

And, as noted by Henning in comments, it is absolutely false. When $D$ is in the interior of the circle circumscribing $ABC$, none of the circles circumscribing $D$ and two of the points in the triangle are contained in the original circle.

  • 0
    Yeah, I missed that it was actually absolutely false. It is obviously false that you can take any triangle to get a "smaller" circle, because if $D$ was very close to $AB$ then the circle containing $ABC$ can be made arbitrarily large.2012-11-13
2

Let $S$ be the given finite set. The convex hull of $S$ is a convex polygon $P$ whose vertices are elements of $S$. Take any two subsequent vertices $p$, $q$ of $P$. The line $g:=p\vee q$ is a supporting line of $S$, i.e., on one side $G^+$ of $g$ there are no points of $S$. Let $h$ be the median line of $p$ and $q$, and consider all circles with center $m\in h$ that go through $p$ and $q$. When $m$ is in $G^+$ and far away of $g$ then the circle will contain no points of $S$ in its interior. Now move $m$ along $h$ to the other side of $g$ and beyond. When $m$ is far away on the other side of $g$ then the circle will contain all points of $S$ (other than $p$ and $q$) in its interior. There has to be a moment in between where the "morphing" circle has still no points of $S$ in its interior, but $\geq3$ points on its boundary.

0

Take the Delauney tesselation of the point set. Every face in this tessellation contains points that lie on a circle, such that there is no other point inside. So every face gives you a set of points that satisfies your constraint.

The tessellation can be computed quite easily. Assign for every point $p_i=(x_i,y_i)$ a height $z_i=x_i^2+y_i^2$. The lower convex hull of the induced 3d point set projects down to the Delaunay tessellation.