Lionel Bouton wrote:
> Hi,
>
> here's my solution. I initially thought that the best circle would be 
> either defined by a diameter (2 points) or one combinations of 3 
> points through which it passes. The idea was that given three points 
> defining a circle a fourth point is either in the circle or defines a 
> circle with 2 from the 3 originals that includes the remaining point.
>
> This would be neat as I wasn't so happy about a gradient walking 
> solution. In this case it can be proven that you can deterministically 
> get the best solution by gradient walking (I don't think there are 
> local maximums) but it's not the general case. Unfortunately it can be 
> proven that such a circle can encircle all points, but not that it's 
> the smallest (and my experiments proved that it isn't).

Update : it seems I was wrong and probably had a bug in this 
implementation as I just read this algorithm described as the best known 
solution until 1983 :-) On the paper referenced by Douglas :

http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/

On a purely random set, my gradient walking is 27 times faster on 10000 
points than Meggido's algorithm (but certainly slower in some cases, 
Douglas' solution gets the result in a fairly constant time for a given 
set size).

Hum, after testing, modifying the initial step for the gradient walking 
from

max width of the set / point_number
to
max width of the set / 4

makes it competitive in all cases (12s on 10000 points instead of 270 
for Meggido's) and not balanced data sets (which random ones are) only.

Lionel