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.
On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> 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.
> On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
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.
> On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote:
> > On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> 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.)
> 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.
) 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
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)?
) ) 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
In <6bc4f385-4b1d-4c1e-b558-37479c4da...@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
Ray Vickson wrote: > 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?
It's obviously polynomial (it's O(N^3) even if you to an exhaustive search over all circles defined by three of the given points).
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.
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.
In article <6bc4f385-4b1d-4c1e-b558- 37479c4da...@k17g2000yqh.googlegroups.com>, and...@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.
>> 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.
People never seem to read the FAQ's anymore, they just FAQ off!
> 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!
n <6bc4f385-4b1d-4c1e-b558-37479c4da...@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.
> In article <6bc4f385-4b1d-4c1e-b558- > 37479c4da...@k17g2000yqh.googlegroups.com>, and...@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.
> On Nov 15, 5:43 am, Chip Eastham <hardm...@gmail.com> wrote:
> > On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote:
> > > On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> > 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:
Chip Eastham <hardm...@gmail.com> wrote: > On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote: > > On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> 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)
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.
Chip Eastham <hardm...@gmail.com> wrote: > On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote: > > On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> 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)
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.
Chip Eastham <hardm...@gmail.com> writes: > Evidently the Welzl algorithm generalizes to > higher dimensions more readily than Meggido's.
And also more easily to other kinds of enclosing figures, such as pairs of parallel lines/planes/hyperplanes. It is also a lot simpler: You can describe Welzl's algorithm in just a few lines of pseudocode:
minCircle(ps) = mC(ps, {})
mC(ps, qs) = the circle defined by (ps ++ qs) if |ps|+|qs| <= 3 mC({p} ++ ps, qs) = let c = mC(ps, qs) in if p is inside c then c else mC(ps, {p} ++ qs)
++ is disjount union of sets.
If you have three points or less, it is easy to find the minimum circle:
- One point gives a zero-radius circle centered at this point.
- Two points define a diameter of a circle.
- Three points define a unique circle that touches all three, but a circle defined by two of these (as above) might be smaller. This is quickly determined.
> > On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote: > > > On Nov 15, 5:29 am, Andrew Tomazos <and...@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. > 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
> 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)
> 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.
I should mention that I'm solving a slightly more general problem: find the smallest circle which contains as subsets a finite number of CIRCLES (not just points).
I'm not convinced this is very different from the original problem.
> In article > <5b980a85-0f88-440e-aabc-a0faf1345...@w19g2000yqk.googlegroups.com>,
> Chip Eastham <hardm...@gmail.com> wrote: > > On Nov 14, 11:54 pm, Andrew Tomazos <and...@tomazos.com> wrote: > > > On Nov 15, 5:29 am, Andrew Tomazos <and...@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:
> > 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
> 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)
> 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.
Hi, Ron:
This is similar to what I read about Meggido's approach, in that his linear programming for the smallest circle gives a problem in 3D, and IIRC for minimum spheres a problem in 4D.
> I should mention that I'm solving a slightly more general problem: > find the smallest circle which contains as subsets a finite number of > CIRCLES (not just points).
> I'm not convinced this is very different from the original problem.
|
