Re: smallest disk covering a set of points

From: amni (amni3_at_hotmail.com)
Date: 05/15/04 

Date: 15 May 2004 12:39:51 -0700

---------

"John T Lowry" <jlowry100@earthlink.net> wrote in message news:<jvnpc.1244$H_3.1171@newsread1.news.pas.earthlink.net>...
> Swinging a couple of arcs from those MaxDist points will show you that
> that's not always a solution.
>
> --
> John T Lowry, PhD
> Flight Physics
> 5217 Old Spicewood Springs Rd, #312
> Austin, Texas 78731
> (512) 231-9391
> jlowry100@earthlink.net
> "amni" <amni3@hotmail.com> wrote in message
> news:e3504803.0405150333.567ccd8d@posting.google.com...
> > Hi suzi,
> >
> > I'm not familiar with this problem but my intuition is to break the
> algorithm
> > to steps: ConvHull and MaxDist.
> >
> > ConvHull
> > Find the convex hull of all the points, as well as the set CH of
> all
> > boundary points of that convex hull.
> > MAxDist
> > Find a pair of points in CH with maximal dustance between them.
> >
> > ConvHull is clearly can be done by simple divide and conquer method,
> > apparently in worst case time O(n log n). Maybe theorethical linear
> > worst case time O(n) can be achived but the algorithm will be
> > consirably more complicated.
> >
> > MaxDist can be done in brute force O(n^2) time but I'll
> > think about faster solutions.
> >
> >
> >
> >
> >
> > Suzi Bevel <sb@example.com> wrote in message
> news:<c8134n$79m$1@news.fas.harvard.edu>...
> > > 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.
> > >
> > > Given:
> > >
> > > -the centre of mass of all the points, (p,q)
> > > -the furthest point from the centre of mass, (c,d)
> > >
> > > I need to calculate the following quantity for each point (i,j):
> > >
> > >
> 1/2*sqrt((-2*p*c+p^2+c^2+q^2+d^2-2*q*d)*(i^2+j^2-2*c*i+c^2-2*d*j+d^2)^2
> > > /((-d^2+d*j+q*d-q*j-c^2+c*i+p*c-p*i)^2))
> > >
> > > and whichever point (i,j) has the *largest* such value, that'll be
> the
> > > radius of my disk. Its centre is given by:
> > >
> > > x =
> > >
> 1/2*(-c*d^2-d^2*p+2*c*q*d+2*d*p*j+c*j^2-p*i^2+p*c^2-p*j^2-c^3+c*i^2-2*c*
> q*j)
> > > /(-d^2+d*j+q*d-q*j-c^2+c*i+p*c-p*i), and
> > > y =
> > >
> 1/2*(-d*c^2-d^3+d*i^2+d*j^2-q*c^2+q*d^2-q*i^2-q*j^2+2*d*p*c-2*d*p*i+2*c*
> q*i)
> > > /(-d^2+d*j+q*d-q*j-c^2+c*i+p*c-p*i).
> > >
> > > Yikes. I'm sure there's a better way. Thanks for any pointers -Suzi.

Quantcast