Prev: Heathfield: You're wrong: here's proof: (WAS: Re: Welcome To The Word Wide Mirror Sci.Math)
Next: SETP-10 Call for papers
From: Ray Vickson on 16 Nov 2009 03:31
On Nov 15, 5:43 am, Chip Eastham <hardm...(a)gmail.com> wrote:
> On Nov 14, 11:54 pm, Andrew Tomazos <and...(a)tomazos.com> wrote:
>
>
>
> > On Nov 15, 5:29 am, Andrew Tomazos <and...(a)tomazos.com> wrote:
>
> > > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a
> > > good algorithm for determining the centerpoint and radius of the
> > > smallest circle that will cover all the points?  Thanks, Andrew.
>
> > (some thoughts)
>
> > If the centerpoint is (x,y),
>
> > than the distance to each point k is given by sqrt((x-ak)^2 + (y-bk)
> > ^2)
>
> > so we want to select (x,y) such as to minimize the largest element of
> > the set:
>
> >    { (x-a1)^2 + (y-b1)^2 ,
> >      (x-a2)^2 + (y-b1)^2 ,
> >      ... ,
> >      (x-an)^2 + (y-bn)^2
> >    }
>
> > But how to do that?
> >   -Andrew.
>
> The short answer is to check out Dave Eberly's
> implementation linked below in the thread!
>
> From what I remember there is a "naive" strategy
> that involves pivoting.  First find the pair of
> points farthest apart; the circle must have at
> least this diameter.  If that diameter (between
> two points farthest apart) yields a containing
> circle, we're done.  If not, the minimum circle
> will have (at least) three points on its
> circumference.  Pick a point outside the given
> "two point" circle, and see if the circle one
> that and the first two points contains all the
> points.  If so, done.
>
> Then you have a sequence of three-point circles
> to consider until you find one that contains
> all the points.  Here's where "pivoting" comes
> into the picture.  We have three points A,B,C
> that determine my current circle, and a point
> D not contained by the circle.  Which point
> A,B,C is to be replaced by D?  A simple way
> to answer this is by trying all three and
> comparing which has the smallest radius yet
> still contains the replaced point.  IIRC a
> slightly more efficient check is based on the
> angles of the resulting triangle.

Assuming that checking for points in/out of a circle, computing a new
circle, etc., are considered as "elementary" operations, is the
problem solvable in polynomial time, or would it be NP-hard? If one
starts out as you suggest, and there are many points outside the
circle, which of those points should be considered as point D? If, at
every new iteration in the procedure we guarantee that more (or not
fewer) points are covered, does that guarantee that the final circle
is optimal? (The procedure sounds vaguely like a "greedy" algorithm,
and such methods are known to be non-optimal in some classes of
problems.)

R.G. Vickson
>
> The inscribed triangle (of three points on
> the circle) must be acute, else the circle's
> radius isn't minimal (having already ruled
> out the two-point circle using two farthest
> apart).  The right choice for D to replace
> is that point which results in the triangle
> with the minimal maximum angle (whose largest
> angle is the smallest among 3 possibilities).
> Since the largest angle opposes the longest
> side, this check can be done via the cosine
> formula for triangles.
>
> regards, chip

From: Willem on 16 Nov 2009 10:58
Andrew Tomazos wrote:
) Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a
) good algorithm for determining the centerpoint and radius of the
) smallest circle that will cover all the points? Thanks, Andrew.

The first idea that springs to mind is to pick some starting center (average
of all points perhaps ?), and draw a circle around that center which
covers all points. And then you 'shrink' the circle, whilst moving
it to keep covering all points, until it can't be shrunk any more.

I think this can be done in a few steps, actually:

- Pick a starting center, C1.
- Find the point farthest away from that center, P1.
- Move the center along the line C1-P1 until the circle C1/P1 touches
another point, P2. Call the new center C2. (*A)
- Call the midway point between P1 and P2, M1.
- Move the center along the line C2-M1, until the circle C1/P1+P2 touches a
third point, P3. (*B)
- You now have the smallest containing circle.

Now, the big challenge is to find quick algorithms for steps *A and *B.
Perhaps that can be done with simple trigonometry and a single loop over
all points. I'll have to consider that.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: Patricia Shanahan on 16 Nov 2009 11:55
Willem wrote:
> Andrew Tomazos wrote:
> ) Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a
> ) good algorithm for determining the centerpoint and radius of the
> ) smallest circle that will cover all the points? Thanks, Andrew.
>
> The first idea that springs to mind is to pick some starting center (average
> of all points perhaps ?), and draw a circle around that center which
> covers all points. And then you 'shrink' the circle, whilst moving
> it to keep covering all points, until it can't be shrunk any more.
>
> I think this can be done in a few steps, actually:
>
> - Pick a starting center, C1.
> - Find the point farthest away from that center, P1.
> - Move the center along the line C1-P1 until the circle C1/P1 touches
> another point, P2. Call the new center C2. (*A)
> - Call the midway point between P1 and P2, M1.
> - Move the center along the line C2-M1, until the circle C1/P1+P2 touches a
> third point, P3. (*B)
> - You now have the smallest containing circle.
....

This seems to constrain solutions to those that have three of the points
on the circle, which was not a requirement in the problem statement. For
example, how would it work with three points, A=(-1,0), B=(1,0),
C=(0,0.5)?

Patricia
From: Willem on 16 Nov 2009 12:05
Willem wrote:
) Andrew Tomazos wrote:
) ) Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a
) ) good algorithm for determining the centerpoint and radius of the
) ) smallest circle that will cover all the points? Thanks, Andrew.
)
) The first idea that springs to mind is to pick some starting center (average
) of all points perhaps ?), and draw a circle around that center which
) covers all points. And then you 'shrink' the circle, whilst moving
) it to keep covering all points, until it can't be shrunk any more.
)
) I think this can be done in a few steps, actually:
)
) - Pick a starting center, C1.
) - Find the point farthest away from that center, P1.
) - Move the center along the line C1-P1 until the circle C1/P1 touches
) another point, P2. Call the new center C2. (*A)
) - Call the midway point between P1 and P2, M1.
) - Move the center along the line C2-M1, until the circle C1/P1+P2 touches a
) third point, P3. (*B)
) - You now have the smallest containing circle.
)
) Now, the big challenge is to find quick algorithms for steps *A and *B.
) Perhaps that can be done with simple trigonometry and a single loop over
) all points. I'll have to consider that.

Never mind, I just realised that this won't work.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: Richard Heathfield on 16 Nov 2009 12:21
In
<6bc4f385-4b1d-4c1e-b558-37479c4dad9f(a)k17g2000yqh.googlegroups.com>,
Andrew Tomazos wrote:

> Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's
> a good algorithm for determining the centerpoint and radius of the
> smallest circle that will cover all the points? Thanks, Andrew.

I think I'd start off with a convex hull, which will give you the
external points, and look for the two points on the hull that are
furthest apart. (I'm not sure that this idea will work unmodified,
but it sounds like a reasonable starting point.)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8
Prev: Heathfield: You're wrong: here's proof: (WAS: Re: Welcome To The Word Wide Mirror Sci.Math)
Next: SETP-10 Call for papers