Determine the radius of the minimum sized circle that encompasses all the points.
Per Smallest Sphere Paper this question was first addressed by Sylvester in 1857, Megiddo in 1982, and optimized by Emo Welzl in 1991.
Input: Points (eg [0 0;0 1;2 0]) Minimum of 3 points
Output: r (radius of optimally centered circle)
Example: [0 0;0 1;2 0] yields [xc,yc,r] [1 .5 1.118] Output r=1.118
Theory: Best Circumcircle may occur in two ways:
1) Center of Line connecting pair with maximum separation, or
2) A circle utilizing three points from the set
Related Challenges:
Warning: Rounding Errors may cause solution errors. Usage of 10*eps(r) may be appropriate.
Strange, as this passes all of the tests on my box. (How did I pass a random test, and fail the hard coded ones?!?) Maybe a bsxfun issue?
Rounding errors of sqrt. Possible fix circle(3)+10*eps(circle(3)) and r+10*eps(r)
Better, but still not quite there. With those fixes, it passes everything but test 2. I'll try a couple more changes, and then just throw in a hard coded hack for case 2. (Or maybe I'll just ask Tim for his solution. :-)
Another astounding solution by Tim using complex numbers and for loops that create vectors. Example of for loop vectorization: for i=nchoosek(3:6,2)',i,end. Very nice mthod.
135 Solvers
Flip the main diagonal of a matrix
388 Solvers
Rotate input square matrix 90 degrees CCW without rot90
250 Solvers
Generate N equally spaced intervals between -L and L
387 Solvers
USC Spring 2012 ACM: Armageddon
11 Solvers