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: spudnik on 16 Nov 2009 14:56
nice, constructive analysis;
wouldn't an approach via the Fermat point
of a trigon, be useful?
(L'Ouvre: http://wlym.com .-)

> Note that the circle must contain 2 of the points. It must also contain the
> longest line segment between any two pairs. The center of the circle must be
> contained in the convex hull of the points. The diameter of the circle must
> be larger or equal to the longest line segment.
>
> If we assume that any optimal circle must have as points the same points as
> longest line segment then we have 2 points. This fixes the center of the
> circle to move along a line that is perpendicular to the line segment
> between the 2 points and also at it's midpoint.
>
> In this case it is very easy to search for the center by subdividing the
> possible center line and noting that it must fall within the convex hull. My
> guess is that the center is the midpoint between the intersection of it and
> the hull. e.g., if it is symmetric then the center is is the midpoint of the
> largest line segment.
>
> I'm not sure if this produces the optimal circle or not and is not unique
> when there are multiple longest line segments.
>
> In terms of convex hulls we are finding the largest line segment contained
> in it and then finding the midpoint of the line segment perpendicular to the
> largest line segment that runs through the largest line segment's midpoint.

--Cap'n Trade & Warren Buffet, together again?
Rep. Waxman's God-am bill, doesn't institute a tarrif, instead!
From: Virgil on 16 Nov 2009 15:26
n
<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.


A reasonable starting 'center point' would be the point having the mean
of the x's and the mean of the y's of the given points as its
coordinates and the starting radius as the distance from that center to
the furthest of the given fixed points.

If there are less than 3 fixed points on the circumference of the
circle, and, if two points, they are not on a diameter of the circle.
the circle can be shrunk by moving its center toward the midpoint of
those points on the circumference and simultaneusly shrinking the radius
to keep the circle passing through those points.

When such shrinkage is no longer possible, one will have the minimal
circle.
From: philippe on 16 Nov 2009 16:17

"Dann Corbit" <dcorbit(a)connx.com> a �crit dans le message de
news:MPG.256b4006e1683e9998969d(a)news.eternal-september.org...
> In article <6bc4f385-4b1d-4c1e-b558-
> 37479c4dad9f(a)k17g2000yqh.googlegroups.com>, andrew(a)tomazos.com says...
>>
>> 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.
>
> Did you read the news:comp.graphics.algorithms FAQ?
> It's in there.
>

Use a lasso that you put all around your points.
It defines an enveloppe.
And other things that you request.

From: Chip Eastham on 16 Nov 2009 22:11
On Nov 16, 3:31 am, Ray Vickson <RGVick...(a)shaw.ca> wrote:
> 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
>
>

Hi, Ray:

What I described is at best O(n^2) given a naive
method for finding the farthest apart pair which
begins the algorithm. My recollection is that
the rest of the algorithm is also O(n^2), since
the radius increases monotonically upward and
thus at each of at most n steps we have to look
for points remaining outside the current circle.

Graphics Gems II by James Arvo gives a somewhat
different O(n^2) algorithm.

The Welzl algorithm used in Dave Eberly's
implementation is O(n^2) in the worst case,
but has much better expected complexity.
As in Dave's code, a random permutation of
the input points is often applied to get
expected linear time complexity.

Good discussion here, touching on generalization
to three dimensions:

[Welzl's Minimum Sphere Algorithm Demystified]
http://www.gamedev.net/reference/programming/features/welzlminsphere/

It is possible to solve the smallest circle
problem in (worst case) O(n) time by linear
programming, as shown by N. Meggido (1983):

[Linear-Time Algorithms for Linear Programming
in R^3 and Related Problems]
http://theory.stanford.edu/~megiddo/pdf/lp3.pdf

See esp. Sec. 4.

Evidently the Welzl algorithm generalizes to
higher dimensions more readily than Meggido's.


regards, chip
From: Ronald Bruck on 18 Nov 2009 03:48
In article
<5b980a85-0f88-440e-aabc-a0faf1345ca9(a)w19g2000yqk.googlegroups.com>,
Chip Eastham <hardmath(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.
>
> 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.

Hmmm. I think I've found a way to solve this using semi-definite
programming.

Call the known points (u_i, vi) with known radius ri. Let (x,y) be the
center of the spanning circle and r its radius. The problem is then to
minimize r subject to the conditions

(*) (ui - x)^2 + (vi - y)^2 <= (r-ri)^2, r >= ri.

This is clearly a quadratic programming problem loosely of SDP type.
We can make it exactly into an SDP problem with a little manipulation.

We consider a family of two-dimensional vectors as the unknowns. (There
are obvious generalizations to balls in R^N.) These include the
vectors e1 and e2 --- the standard orthonormal basis --- which we
regard as unknowns by the fiction that they are unknown but satisfy the
relations

(1) <ei, ej> = Kronecker-delta (i,j).

The only other unknowns are the (really!) unknown X = (x,y) and R =
(r,0). These satisfy the equations

(2) <R,e1> = r, <R,e2> = 0.

Then the constraint (*) becomes

(**) ui^2 + vi^2 - ri^2 <= r^2 - 2 r ri + 2 ui x + 2 vi y - (x^2 + y^2)

= <R,R> - 2ri <R,e1> + 2 ui <X,e1> + 2 vi <X,e2> - <X,X>

The problem is to minimize r = <R,e1> subject to (**) and the
additional constraints that

<X,e1> >= ri for all i.

and that's why it's an SDP problem: the Gramian of the vectors e1, e2,
R and X is positive semi-definite, and the problem is one of minimizing
one element of the Gramian (<R,e1>) subject to linear constraints on
the elements of the Gramian.

I'm currently finishing a paper where I did a similar thing for
intersecting spheres (closed balls) in R^N. It turns out to be rather
efficient. THAT application even allowed us to find proximinal points
on intersections of spheres, COMPLEMENTS of spheres, and closed
half-spaces (a problem which is not generally convex).

One catch with SDP is that you can't really specify the dimension in
which the problem lives. In particular, you would have to check
whether

<X,X> = <X,e1>^2 + <X,e2>^2.

I suspect you'll find solutions where this isn't true, that the SDP
lives in dimension 3 or 4; but that with a little manipulation you can
bring it down to dimensions 2. (You can't just toss that last equation
in as a constraint, because it's not a LINEAR constraint.)

I'll try programming a few problems and see what happens.

-- Ron Bruck
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