Smallest Enclosing Circle problem

[Disch]

For those unfamiliar:
http://en.wikipedia.org/wiki/Smallest-circle_problem

Basically you are given a set of points in 2D space, and your goal is to find the smallest possible circle which encloses all the points.


There are numerous solutions to this problem. Even some that are in O(n) time. However I have having the hardest time wrapping my head around any of them... as they all seem to be explained very cryptically and with no visual aid.

Can anyone link me to a page that actually explains a reasonable solution to this problem in somewhat simplistic terms?

[giblit]

I would assume first you have to find the two points that are the furthest apart and that would be the diameter. Though I could be wrong. But that would be O(n) to compare all the points. Sounds like a pretty interesting problem. Actually I think that would be worse than O(n)

[Disch]

Furthest two points would not work. Think of the 3 points of an equilateral triangle

And checking distance between all points would be O(n*n)


EDIT:

If I could just even figure out how to do it for 3 points .... I devised a solution that might work for my purposes that I can build off that.


EDIT:

Okay, the search term I needed was "circumcenter", and it's extremely easy to obtain from any given 3 points. Lemme see if I can make a working implementation now.

[giblit]

Good catch. How about finding the "center" of all points. Then from there find the point that has the furthest distance and that be the radius? Though this would be another slow solution.

With your example an equilateral triangle.

Point 1 = 3, sqrt(3) +2 ~ 3.732
Point 2 = 2,2
Point 3 = 4,2
Center = (x1+x2+x3)/3, (y1+y2+y3)/3 = 3,2.577350269189625764509148780502 ~ 3, 2.577

Then since this is a equilateral they will all be same distance so I will only test one (but for a bunch of points you would need to test all and find the largest distance)

Which gives a radius of 1.1547005383792515290182975610039 ~ 1.155

Again, I could be completely wrong :P

Edit yeah the circumcenter looks like what you want so you can probably ignore what I said

[ResidentBiscuit]

Hmm interesting problem. Found this describing the major solutions:
http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Even has an applet that lets you place points to see the O(n) solution in action.

[Disch]

@ResidentBiscuit: Yeah I saw that... that was one of the ones that was too cryptic for me to follow.

Preferably if something could explain the logic behind the algorithm instead of just throwing magic math at me, that would be best.


EDIT:

Also, my idea for my own solution doesn't work.

EDIT 2:

Giving it another read. The Applet's Algorithm seems like I could wrap my head around it, but it makes no mention of time complexity. I guess I can figure that out on my own.

[ne555]

> Okay, the search term I needed was "circumcenter"
that's the center of the circumference that pass for all the points.
It is not what you want; think of an obtuse triangle, you'll use the furthest point as diameter in that case.

> If I could just even figure out how to do it for 3 points
brute force. They are only 3 points, that's the base case.


> However I have having the hardest time wrapping my head around any of them...
> as they all seem to be explained very cryptically and with no visual aid.
Try Computational Geometry Algorithms and applications by de Berg, it explains the randomized incremental with linear programming.

You start with 2 points, they define the circle.
You add new points, if they are inside the circle, then your previous solution is good enough.
If the new point lies outside the circle, you know that this point would be on the boundary of the MEC

[Disch]

ne555 wrote:

that's the center of the circumference that pass for all the points.
It is not what you want; think of an obtuse triangle, you'll use the furthest point as diameter in that case.

Yes but it's what I want for a situation where the triangle is acute. I already ruled out obtuse triangles elsewhere in my algorithm.

But it doesn't matter because that algorithm didn't work. =P

ne555 wrote:

You start with 2 points, they define the circle.
You add new points, if they are inside the circle, then your previous solution is good enough.
If the new point lies outside the circle, you know that this point would be on the boundary of the MEC

Yeah it's on the boundary of the MEC until you find another point that is not in that MEC... at which time the points on the boundary can change completely.

Try Computational Geometry Algorithms and applications by de Berg, it explains the randomized incremental with linear programming.

Thanks, but I'd rather not get and sift through a whole book just for this one problem. Can you link me to an online copy of the relevant part of that book?



EDIT:

Actually... the Chrystal algorithm on Resident Buscuit's link is very straightforward. That might be what I need.

I think it was just the Megiddo algorithm that was confusing me before.

The trick now is finding the convex hull. The page sort of glosses over how to do that efficiently.

[ne555]

> Yeah it's on the boundary of the MEC until you find another point that is not in that MEC...
> at which time the points on the boundary can change completely.
that's the incremental part
you have the MEC for points 1 to k.
If point k+1 lies inside that circle, the MEC remains.
If it lies outside, then the MEC for points 1 to k+1 pass over k+1

So you traverse 1 to k again, to find a circle that contains them all, and that passes over k+1


> Can you link me to an online copy of the relevant part of that book?
here you are
http://www.mediafire.com/view/neegrygvk2h4szv/computational_geometry_deberg.pdf


> The trick now is finding the convex hull.
there is one incremental algorithm that uses the sorted by x property.
http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/incrementCH.htm