On 2008-02-17, Justin Ethier <justin.ethier / gmail.com> wrote:
> Hello,
>
> Had a lot of fun with this one :) My solution works by taking the average of
> all points as the center, and the farthest outlying point as the radius. An
> optimal solution is then found by moving the circle center towards the
> outlier as the radius is reduced, while all points still are within the
> radius. The same principles could be applied for higher dimensions as well.

Nice solution, this was also one of my first ideas. The problem with
this approach is if many points are close to each other and only few
points are far away. In this case the center is near that mass of points
and the line-search may fail to find an optimal solution. For example:

puts encircle( ([[0.0,0.0]] * 100 + [[0.0,1.0], [1.0,0.0]]).map{|p|
        Point.new(*p)})

(100 points at (0,0), one at (1,0) and one at (0,1)) gives a solution of
{center:(0.00980392156862745, 0.00980392156862745), radius:0.990244611507173}
but optimal would be (1/2, 1/2) and radius 1/sqrt(2). 

Frank