Problem of the Week 993

Find an Empty Circle

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.