From: Philipp Hofmann <phil@...126.de>
Date: 2008-02-20T10:00:46+09:00
Subject: Re: [QUIZ] The Smallest Circle (#157)


On Wed, Feb 20, 2008 at 07:20:06AM +0900, Lionel Bouton wrote:
>
> 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.

sorry, I haven't come across a public paper of clarkson's algorithm,
either. But it's proven that the algorithm has O(log(n)), n of course
being the number of given points.

I'm not going to do a full proof here, but it's an outline.

You need at max 3 points to describe the smallest enclosing circle. If
you haven't found it yet you increase the chance of every point that is
outside a circle determined by 13 random points each turn, by
doubleing their relative frequencies.

After k iterations at least one of the (at max) three points you are
looking for has a relative frequency of 2**(k/3)

In average the sum of relative frequencies is increased by a factor of
1+3/13 each iteration.

For an increasing k this leads to a paradox: Because at some point the
relative frequency of at least one point 2**(k/3) would exceed the
overall sum of relative frequencies (n*(1+3/13))**k, if the algorithm
hadn't come to an end, yet.

The only reference I found on the net where it is at least partially
explained and where I got the outline for the proof from is this (but
be warned, it's in german):

  http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo42.php


> 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 :-)

Even if this one seems to be more about the algorithm, we still do it
in Ruby, right? ;) Anyway we'll see what our brand new quizmaster will focus
on. ;)

g phil