Philipp Hofmann wrote:
>
> What you call a 'badly shaped point clouds' is in fact an approximate
> circle.

In fact initially I tested with a disk (which is an intermediate level 
before the circle for the number of points on the convex hull), the 
worst shape is indeed a circle (when you replace ro by a constant in my 
random method for people still following) : the number of polygone 
vertices is then the total number of points.

> I confident it doesn't do any harm to your poor laptop this time. ;)
>   

The little thing survived ! Clarkson's is good for the worst case (every 
point on the same circle) which fits common sense (any circle should 
encircle all points, so the first iteration should win minus rounding 
errors in floating point computations), it's nearly 3x as fast as the 
gradient walking in this case. The speed doesn't change too much given 
various random shape (between 2 to 4s on my laptop). The gradient 
walking still wins when a small portion of the points are on the convex 
hull (random on a disk for example: 0.5s vs 4s).

I believe gradient walking should be faster when less than one third of 
the points are on the convex hull, slower in the other case, but it's a 
rough estimation based on observed behavior.

One thing that I don't like though is that the total time is difficult 
to predict. Probabilistic algorithms often have good performance but I'm 
always uneasy when I'm not sure how much time they can spend before 
returning and even when they will exhibit bad behaviour. It's a matter 
of constraints in which the code must fit and I mostly have to return 
results in a timely manner in most of my projects :-)

Is there any public paper describing the performance behavior of the 
algorithm? All scientific papers returned by Google point to 
paid-subscription materials.

Lionel

PS: is it me or is this becoming more an algorithm-Quiz than a 
Ruby-Quiz? It's my first Quiz and I was expecting to see some clever use 
of Ruby, but in this kind of Quiz I don't see much place for elegant code.
Not that I complain: I love to study the performance of algorithms too :-)