Path: utzoo!mnetor!uunet!husc6!think!ames!elroy!mahendo!jplgodo!wlbr!etn-rad!jru
From: jru@etn-rad.UUCP (John Unekis)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <498@etn-rad.UUCP>
Date: 5 Apr 88 19:00:51 GMT
References: <496@etn-rad.UUCP> <494@eos.UUCP>
Reply-To: jru@etn-rad.UUCP (John Unekis)
Organization: Eaton Inc. IMSD, Westlake Village, CA
Lines: 25

In article <494@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes:
>In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes:
>>I am looking for an efficient algorithm that, given a set of points, finds the
>>smallest circle enclosing them and its center.  Pseudocode, actual code (C,
>
>A number of people have proposed solutions involving picking a center,
>(by averaging?) and then getting the radius as the distance to the
>most distant point.  A key observation is that for the *smallest* circle,
>there will be three points which lie on the circle.  Think about it:
>if the circle encloses all the points and only contains two of the points,
>then you can shrink the radius (while staying on the two points) until
>the circle contains another point.  This suggests an algorithm which,
...
There is an obvious fallacy here. take the set of points 
{(-7.07,7.07),(0,10),(7.07,7.07)}
A circle that had three points along the edge would have a center at (0,0)
and a radius of 10. However a circle with center at (0,7.07) and radius 7.07
contains all three points and has a smaller radius with only two points on 
the circle. I beleive that in general you can shrink a circle which has only
one point from the set on the circumference until it has two, but to get a 
third point on the circumference may require the circle to GROW, not shrink.
Note that my original solution doesn't give the smallest radius either, so
we are still waiting for a correct solution.