Re: [QUIZ] The Smallest Circle (#157)

Philipp Hofmann wrote:
> Here is my solution. Although it uses a brute force approach if the
> first attempts (driven by obvious constraints) of determining the
> circle fail, it scales on larger sets, because the given equal
> distibution of random points form an approximate square on these
> sets.

Wow, that was awfully fast for the random distribution, it takes more 
time to display the result than computing it even on 10000 points !

On badly shaped point clouds it suffers greatly, I couldn't get it to 
compute the circle for 1000 points if I feed it with :

class Point < Struct.new(:x, :y)
  def self.random
    ro = rand / 2
    theta = Math::PI * 2 * rand
    Point.new(ro * Math::cos(theta) + 0.5, ro * Math::sin(theta) + 0.5)
  end
[...]
end

The ruby process happily took more than 800MB and I had to kill it while 
I could still get some feedback from my poor laptop :-)


Note :
I found it suspicious that I could get better performance than the 
accepted best mathematical solution in the general case and I reflected 
a while on that.
I think the reason why the gradient walking is faster is because it is 
inherently inaccurate. Megiddo's algorithm defines the exact position of 
the center using a geometrical process. Unfortunately computers must 
manipulate floating point data when describing points, segments, 
vectors, circles, ... So any computer result is inherently inaccurate.
The gradient walking method profits from this inaccuracy: it stops when 
the step becomes too small to move the current best position because of 
rounding errors. This happens in o(n) steps where n is the number of 
bits used to represent the floating point mantissa which is a huge win 
(I don't remember the actual number of bits, but it must be < 64) 
compared to the o(n) of Megiddo's where n is the number of *points*.



I benched the hull computing method and I believe that we can get the 
best of both worlds : on any distribution of points I threw at it 
(random in a square, in a disk or on a circle) computing the convex hull 
took 0.4s for 10000 points on my laptop. To be as fast as possible, we 
could run your algorithm up to the point where it switches on the brute 
force method. Then, instead of looking for the best circle based on 
three points of the hull, we'd use the gradient walking method. Using 
only the hull points saves time in the most common cases and the 
filtering is quick enough to be negligible in the worst case when no 
point can be filtered out.

My tests only filtering the points using your ConvexHull class before 
applying gradient walking returns in 0.5s for the initial distribution 
(on a square) or on a disk and fall back to 12-13s on the worst case: 
distribution on a circle.

Lionel.