From: "Frank Fischer" <frank.fischer / s2001.tu-chemnitz.de>
> On 2008-02-17, Justin Ethier <justin.ethier / gmail.com> wrote:
>>
>> 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).

My variation using an axis-aligned bounding box to pick the
initial center point appears to handle the above case.

However I would not be surprised if it still might find some
sub-optimal solutions.... :-/


Regards,

Bill