On 2/20/08, Rick DeNatale <rick.denatale / gmail.com> wrote:
> Here's my solution.
>
>  I also eschewed doing any google research and started from scratch.  I
>  think I've taken a slightly different approach than any already
>  described.
>
>  The basic approach is to start with a circle containing only the first
>  point, and then add the points one by one changing the circle as
>  necessary.  So
>
>  First point
>    Set center to the point and radius to zero.
>
>  Subsequent points.
>    If the point is already in the circle then the point is simply
>  added to the collection of points and the circle is unchanged.  The
>  point is in the circle if the distance from the center of the circle
>  is less than the radius (within some epsilon to deal with floating
>  point comparisons).
>
>   If the point is further from the center than the radius, the we know
>  that it must lie on the circumference of the new circle which will
>  contain all of the points examined thus far.  We now find the set of
>  points which are furthest from the new point (again within some
>  epsilon).  There will of course be one or more of these points.
>
>   Now the center of the new circle is the average of those furthest
>  points plus the new points, and the radius is the distance between the
>  center and the new point.

Oh, well, it was a good try I guess, but I ran afoul of the case
exposed by Alex Shugin.  The points farthest from the new point don't
necessarily (all) have to be on the circumference of the circle.

-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/