Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What if the 4 points are in a square arrangement? The (unique) circle through any three automatically contains the 4th, right? Or am I missing something? –  Jason DeVito Nov 13 '12 at 13:24
    
@JasonDeVito But no points in it (as there are only these four point. Note that "... formed with three or more points ..." refers to the points on the circle. –  martini Nov 13 '12 at 13:29
1  
Do you mean to say "there exists a circle passing through three of the points such that none of the points lies in the interior of that circle? Normally "lying in a circle" isn't meaningful, and most readers will take it to be a mistyping of "lying on a circle". –  Marc van Leeuwen Nov 13 '12 at 13:29
2  
Assuming my interpretation is right, your "proof" doesn't work, since with the point inside the circle and the points on the circle (which are the only points in your set that you know anything about) you cannot create a new circle that is entirely contained in the interior of original circle. –  Marc van Leeuwen Nov 13 '12 at 13:33
    
@JasonDeVito I think he means no points in the interior. –  Thomas Andrews Nov 13 '12 at 13:46

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
1  
If is not only false, it is so false that it is never true. If $D$ is any point in the interior of any triangle $ABC$, then the circumcircle of $ABD$ will extend outside the circumcircle of $ABC$. –  Henning Makholm Nov 13 '12 at 13:59
    
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. –  Thomas Andrews Nov 13 '12 at 16:36

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.