izard: (Default)
[personal profile] izard
Those interview questions... I am not fond of computer science riddles, but some are.

I am reasoning about Welzel's algorithm complexity:
(to find a minimal bounding circle over set of points P, there is a recursive algorithm:
circle mbcr(P[n], R)
if |P| = 0 or |R| = 3
return get_circle(R)
if (P[0] in mbcr(P-P[0], R))
return mbcr(P-P[0], R)
return mbcr(P-P[0], R+P[0])

In a textbook, they say complexity is ϴ(n) for average case and O(n^2) in worst case..

I am getting different values. Lets assume worst case, when "if (P[0] in mbcr(P-P[0], R))" is always false.
mbcr(n, |R|=3) = O(1) - obviously.
mbcr(n, |R|=2) = O(n) - n * first recursion point, and each time it gets only once to second recursion point (which is mbcr(n, |R|=3) case).
mbcr(n, |R|=1) = O(n^2) - T(mbcr(n, |R|=1)) = O(n) + (n-1) * T(n-1, |R|=2)) = O(n + n^2) = O(n^2)
mbcr(n) = O(n^3) - T(mbcr(n)) = O(n) + (n-1) * (T(mbcr(n-1,|R|=1)) = O(n) + O(n^3) = O(n^3)

What am I missing?? Everything above seems very clear for me, can't stop thinking about this simple problem.

Date: 2017-04-19 08:00 pm (UTC)
sab123: (Default)
From: [personal profile] sab123
First, an obvious moment that they should cache the result of mbcr(P-P[0], R) to avoid calling it twice. If I remember right, calling it twice will make the run time exponential. It's exponential and not quadratic because adding an extra point would double the amount of computation.

Now let's consider the best case. What is the best case? It's when the last 3 points form the boundary of a circle where all the other points fit. In this case the run time will obviously be linear, just computing mbcr(P-P[0], R) on each step.

What is the worst case then? If each point doesn't fit into the circle formed by all the following points. So on each step it would first compute mbcr(P-P[0], R) and then mbcr(P-P[0], R+P[0]). So if the cost of both were linear, this also would be exponential and not quadratic. And I think they are. mbcr(P-P[0], R) is obviously at least linear. mbcr(P-P[0], R+P[0]) seems to be limited by R reaching the size of 3. But before it tries to grow R, it would still try to recurse down all the way in its nested call of mbcr(P-P[0], R) which is linear. Thus I think that this specific algorithm is exponential.

But maybe it can be converted to a quadratic one:

Start with 3 points. They obviously define a circle.
while there are more points {
Add the next point.
If it falls within the existing circle, this is the easy case.
Otherwise try every combination of (the new point, two of 3 previous boundary points). This step will be linear because it needs to check the resulting circle against every other point, and the number of attempts is always fixed to 3.

The part I'm not sure about is whether replacing 1 point in 3 would always be enough to form a new circle that includes everything but it's a reasonable guess.


izard: (Default)

September 2017

3456 789
1718 1920212223

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 12:15 am
Powered by Dreamwidth Studios