Hosted by The Math Forum

Problem of the Week 993

Find an Empty Circle

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Let S be a set of points in the plane, at least three and and not all on a straight line. Show how one can find three points in S so that the circle through them has no points of S in its interior.

For example: One could say: Draw all circles. For each one check whether all other points are outside. Then select the circle that works. But (1) this does not prove that there is a circle that works; second, if there are n points in the set, then this could take n^3 steps for the circles and n checks for each one, so it would be an algorithm that takes about n^4 steps. The idea is to find an algorithm that is quite a bit faster.

Source: Crux Mathematicorum, Feb 2003 (from an Estonian Olympiad, 1996-97), but the problem is quite well known to computational geometers.

© Copyright 2003 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


16 October 2003