From: ThoML <micathom@...>
Date: 2008-02-20T21:45:05+09:00
Subject: Re: The Smallest Circle (#157)

> I don't quite understand how to interpret the numbers?
>
> But I have to ask.. which is billk vs. billk2 ?  If billk2 is less
> accurate, would I be correct in assuming it is the naive bounding
> box version?

billk2 is the revised version. The maximum distance is lower, thus
it's more accurate. Basically, you'd want a 0.0 in all cells.

min ... minimal distance to the winner (smallest circle)
max ... maximal distance to the winner
avg ... average (arithmetic mean) distance to the winner

The table doesn't contain info about the diameter. I suppose a
relative measure would be more useful. Hm.

Here are two runs with relative numbers. The relevant measure is the
circle radius. The numbers are the distance in per cent of the correct
solution's radius.

     s_tml.rb | s_billk.rb | s_billk2.rb | s_lionel.rb | s_frank.rb |
s_justin.rb
Min: 0.00     | 0.00       | 0.00        | 0.00        | 0.15       |
0.00
Max: 15.77    | 17.72      | 7.81        | 4.98        | 2.13       |
9.28
Avg: 0.54     | 4.79       | 1.18        | 0.43        | 1.03       |
1.38

      s_tml.rb | s_billk.rb | s_billk2.rb | s_lionel.rb | s_frank.rb |
s_justin.rb
Min:   0.00    | 0.00       | 0.00        | 0.00        | 0.11       |
0.00
Max:   5.37    | 15.99      | 7.39        | 5.80        | 2.01       |
12.10
Avg:   0.36    | 5.07       | 1.07        | 0.35        | 1.01       |
1.38

Okay, now with Lionel's current version:

     s_tml.rb | s_billk.rb | s_billk2.rb | s_lionel.rb | s_lionel4.rb
| s_frank.rb | s_justin.rb
Min:   0.00   | 0.00       | 0.00        | 0.00        | 0.00
| 0.26       | 0.00
Max:   4.79   | 18.35      | 9.15        | 3.33        | 4.66
| 1.95       | 17.57
Avg:   0.54   | 5.44       | 1.20        | 0.22        | 0.36
| 0.99       | 1.76

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.

Regards,
Thomas.