From: Lionel Bouton <lionel-subscription@...>
Date: 2008-02-20T22:20:29+09:00
Subject: Re: The Smallest Circle (#157)

ThoML wrote:
> [...]
>
> As you can see, may solution fails noticably on certain point sets but
> does more or less well in average. At least for random point sets. I
> think Justin's solution suffers from the same problem since his
> approach is quite similar, only that he moves the center gradually bit
> by bit while my "solution" ... well, let's not talk about that.
>
> The performance of Frank's solution is quite constant albeit slightly
> imprecise.
>
> I didn't include Douglas's and Philip's solutions since they are
> precise.
>   

I'm not sure that you can draw a clear line between Douglas, Philip, 
Justin and my solution versus precision. I've not studied the results of 
each precisely and I've only read through the algorithms quickly, but my 
guess is that:
- Douglas and Philip are theoretically correct and Justin and mine are 
theoretically incorrect.
- that said you must keep in mind that floating point computations are 
inherently incorrect most of the time.

So solutions relying on defining circles by 3 points (which uses line 
intersections with a good deal of add and multiply on floating point 
values) might and most probably often do give circles that don't include 
one of the points it is supposed to pass through.

In fact Justin and me have solutions that often give suboptimal 
solutions but:
- within a predictable range of the ideal solution (a small multiple of 
the floating point error).
- as they rely on the max_distance from a point to the point cloud the 
circle is guaranteed to include all points.

Lionel