Re: smallest disk covering a set of points

From: Paul Hsieh (qed_at_pobox.com)
Date: 05/14/04 

Date: 14 May 2004 10:40:47 -0700

Suzi Bevel <sb@example.com> wrote:
> Is there a fast algorithm for finding the smallest disk that covers a set
> of points in the plane?
>
> My idea has proved very inefficient: I found the centre of mass, shrunk a
> circle till I hit the outermost point, then simultaneously shrank the
> radius and moved the centre closer to that outermost point, keeping it on
> the circumference, until I hit a second point somewhere with the shrinking
> circumference, and that's where I stopped. Apart from giving horrid
> expressions for the centre and radius, I don't even know whether this
> process works.

I dunno -- I kind of doubt it. (Don't they teach you harvard weenies
about convex hulls?)

This is what I would do:

Step 1: Find the minimal set of points which generates the convex hull
of the set of points. I.e., any point on the *inside* of the convex
hull, just remove it. I think there are well known linear time
algorithms for this. (Also remove points on the interiors of the
convex hull edge -- so no three points remaining are colinear.)

Step 2: Choose the first of the remaining points, and construct the
circle. We call these three points the active points.

Step 3: Remove any points inside this circle. If there are no points
outside the circle we are done, otherwise proceed to step 4.

Step 4: Choose any random point outside the circle, and call it p.
Substitute p for each one of the three points in turn then perform
step 3 which each of the three possible circles. If the algorithm
does not terminate, we know that one of the original three points will
be eliminated. When that happens, we can replace it with p and return
to the beginning of this step (step 4.)

Which looks like a linear time minimum circle finding algorithm to me. 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: smallest disk covering a set of points
    ... Convex hull of an arbitrary set of points can not be found in O ... In fact, no algorithm ... > outside the circle we are done, ...
    (comp.programming)
  • Re: Help with bisectors
    ... Once you get your implementation ready you'll see how roundoff errors totally breaks your algorithm in most real cases, and you'll spend months, many, trying to fix it with little success, unless you happen to have a lot of experience in robust geometric computing. ... I strongly recommend that you simplify the problem by linearizing the circular arcs. ... (precisely line-arc bisectors and arc-arc ... circle-circle bisectors are ellipses, or hyperbolas, if they are unconnected. ...
    (comp.graphics.algorithms)
  • Re: smallest disk covering a set of points
    ... If there is a 4th point outside the second circle on ... iteration" when an algorithm is found to fail more often fails ... my intuition tells me that it will converge to ...
    (comp.programming)
  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (comp.games.development.programming.algorithms)
  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (sci.math)