How to show things on a plane?

Question

In national mathemathics magazine i found some cool task. On a plane we have finite amount of points. Any three of them are not colinear. Show that there exist circle ( formed with three or more points ) that doesn't contain other points in it.

My logic is quite simple. Assume we have some circle created from 3 or more points. If in this circle(interior) exist 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.

Is there more elegant way to prove such things?

Thanks...

Answer 1

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.

Answer 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.

Answer 3

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.