COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Smallest circle covering set of points

• Email
• Follow

```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.
```
 0
Reply Andrew 11/15/2009 4:29:38 AM

See related articles to this posting

```On Nov 15, 5:29=A0am, 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? =A0Thanks, 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.
```
 0
Reply Andrew 11/15/2009 4:54:30 AM

```On Nov 15, 5:54=A0am, Andrew Tomazos <and...@tomazos.com> wrote:
> =A0 =A0 =A0(x-a2)^2 + (y-b1)^2 ,

typo
(x-a2)^2 + (y-b2)^2 ,
```
 0
Reply Andrew 11/15/2009 4:57:56 AM

```Le Sat, 14 Nov 2009 20:29:38 -0800 (PST)
Andrew Tomazos a �crit
>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.

Look at the Meggido's algorithm, i don't know if there is a PDF paper
somewhere, but there is this quick review :

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Also, you can use something that already exists as Miniball which is
part of CGAL :

http://www.inf.ethz.ch/personal/gaertner/miniball.html

--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...
```
 0
Reply zwim 11/15/2009 5:11:19 AM

```"Andrew Tomazos" <andrew@tomazos.com> wrote in message
> 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 algorithm is called Welzl's algorithm (see the Miniball reference posted
by zwim).
I also have an implementation,
http://www.geometrictools.com/LibFoundation/Containment/Containment.html
files Wm4ContCircle2.{h,cpp}

--
Dave Eberly
http://www.geometrictools.com

```
 0
Reply Dave 11/15/2009 5:31:00 AM

```On Nov 14, 11:54=A0pm, Andrew Tomazos <and...@tomazos.com> wrote:
> On Nov 15, 5:29=A0am, 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? =A0Thanks, 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:
>
> =A0 =A0{ (x-a1)^2 + (y-b1)^2 ,
> =A0 =A0 =A0(x-a2)^2 + (y-b1)^2 ,
> =A0 =A0 =A0... ,
> =A0 =A0 =A0(x-an)^2 + (y-bn)^2
> =A0 =A0}
>
> But how to do that?
> =A0 -Andrew.

The short answer is to check out Dave Eberly's

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
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
```
 0
Reply Chip 11/15/2009 1:43:18 PM

```On Nov 15, 5:43=A0am, Chip Eastham <hardm...@gmail.com> wrote:
> On Nov 14, 11:54=A0pm, Andrew Tomazos <and...@tomazos.com> wrote:
>
>
>
> > On Nov 15, 5:29=A0am, 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? =A0Thanks, 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:
>
> > =A0 =A0{ (x-a1)^2 + (y-b1)^2 ,
> > =A0 =A0 =A0(x-a2)^2 + (y-b1)^2 ,
> > =A0 =A0 =A0... ,
> > =A0 =A0 =A0(x-an)^2 + (y-bn)^2
> > =A0 =A0}
>
> > But how to do that?
> > =A0 -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. =A0First find the pair of
> points farthest apart; the circle must have at
> least this diameter. =A0If that diameter (between
> two points farthest apart) yields a containing
> circle, we're done. =A0If not, the minimum circle
> will have (at least) three points on its
> circumference. =A0Pick a point outside the given
> "two point" circle, and see if the circle one
> that and the first two points contains all the
> points. =A0If so, done.
>
> Then you have a sequence of three-point circles
> to consider until you find one that contains
> all the points. =A0Here's where "pivoting" comes
> into the picture. =A0We have three points A,B,C
> that determine my current circle, and a point
> D not contained by the circle. =A0Which point
> A,B,C is to be replaced by D? =A0A simple way
> to answer this is by trying all three and
> comparing which has the smallest radius yet
> still contains the replaced point. =A0IIRC 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). =A0The 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

```
 0
Reply Ray 11/16/2009 8:31:48 AM

```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
```
 0
Reply Willem 11/16/2009 3:58:04 PM

```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
```
 0
Reply Patricia 11/16/2009 4:55:31 PM

```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
```
 0
Reply Willem 11/16/2009 5:05:11 PM

```In
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
```
 0
Reply Richard 11/16/2009 5:21:05 PM

```[F'up2 sorely missing --- fixed]

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).
```
 0
Reply ISO 11/16/2009 6:14:31 PM

```Megiddo's Linear-Time Algorithm?
--
Regards,
Casey
```
 0
Reply Casey 11/16/2009 6:50:21 PM

```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.

```
 0
Reply Jon 11/16/2009 6:55:20 PM

```In article <6bc4f385-4b1d-4c1e-b558-
>
> 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.

```
 0
Reply Dann 11/16/2009 6:55:39 PM

```On Mon, 16 Nov 2009 10:55:39 -0800, Dann Corbit <dcorbit@connx.com>
wrote:

>In article <6bc4f385-4b1d-4c1e-b558-
>>
>> 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!

--
Regards,
Casey
```
 0
Reply Casey 11/16/2009 7:27:50 PM

```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!
```
 0
Reply spudnik 11/16/2009 7:56:48 PM

```n
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.
```
 0
Reply Virgil 11/16/2009 8:26:54 PM

```"Dann Corbit" <dcorbit@connx.com> a �crit dans le message de
news:MPG.256b4006e1683e9998969d@news.eternal-september.org...
> In article <6bc4f385-4b1d-4c1e-b558-
>>
>> 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.

```
 0
Reply philippe 11/16/2009 9:17:51 PM

```On Nov 16, 3:31=A0am, Ray Vickson <RGVick...@shaw.ca> wrote:
> On Nov 15, 5:43=A0am, Chip Eastham <hardm...@gmail.com> wrote:
>
>
>
> > On Nov 14, 11:54=A0pm, Andrew Tomazos <and...@tomazos.com> wrote:
>
> > > On Nov 15, 5:29=A0am, 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? =A0Thanks, 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:
>
> > > =A0 =A0{ (x-a1)^2 + (y-b1)^2 ,
> > > =A0 =A0 =A0(x-a2)^2 + (y-b1)^2 ,
> > > =A0 =A0 =A0... ,
> > > =A0 =A0 =A0(x-an)^2 + (y-bn)^2
> > > =A0 =A0}
>
> > > But how to do that?
> > > =A0 -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. =A0First find the pair of
> > points farthest apart; the circle must have at
> > least this diameter. =A0If that diameter (between
> > two points farthest apart) yields a containing
> > circle, we're done. =A0If not, the minimum circle
> > will have (at least) three points on its
> > circumference. =A0Pick a point outside the given
> > "two point" circle, and see if the circle one
> > that and the first two points contains all the
> > points. =A0If so, done.
>
> > Then you have a sequence of three-point circles
> > to consider until you find one that contains
> > all the points. =A0Here's where "pivoting" comes
> > into the picture. =A0We have three points A,B,C
> > that determine my current circle, and a point
> > D not contained by the circle. =A0Which point
> > A,B,C is to be replaced by D? =A0A simple way
> > to answer this is by trying all three and
> > comparing which has the smallest radius yet
> > still contains the replaced point. =A0IIRC 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). =A0The 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
```
 0
Reply Chip 11/17/2009 3:11:21 AM

```In article
Chip Eastham <hardmath@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:
> >
> > � �{ (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

<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
```
 0
Reply Ronald 11/18/2009 8:46:54 AM

```In article
Chip Eastham <hardmath@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:
> >
> > � �{ (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

<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
```
 0
Reply Ronald 11/18/2009 8:48:56 AM

```Chip Eastham <hardmath@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.

Torben
```
 0
Reply torbenm 11/18/2009 1:04:43 PM

```In article <181120090046541409%bruck@math.usc.edu>, Ronald Bruck
<bruck@math.usc.edu> wrote:

> In article
> Chip Eastham <hardmath@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.

> 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.

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.

-- Ron Bruck
```
 0
Reply Ronald 11/20/2009 5:06:36 PM

```On Nov 18, 3:46=A0am, Ronald Bruck <br...@math.usc.edu> wrote:
> In article
>
>
>
> Chip Eastham <hardm...@gmail.com> wrote:
> > On Nov 14, 11:54=A0pm, Andrew Tomazos <and...@tomazos.com> wrote:
> > > On Nov 15, 5:29=A0am, 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? =A0Thanks, 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:
>
> > > =A0 =A0{ (x-a1)^2 + (y-b1)^2 ,
> > > =A0 =A0 =A0(x-a2)^2 + (y-b1)^2 ,
> > > =A0 =A0 =A0... ,
> > > =A0 =A0 =A0(x-an)^2 + (y-bn)^2
> > > =A0 =A0}
>
> > > But how to do that?
> > > =A0 -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. =A0First find the pair of
> > points farthest apart; the circle must have at
> > least this diameter. =A0If that diameter (between
> > two points farthest apart) yields a containing
> > circle, we're done. =A0If not, the minimum circle
> > will have (at least) three points on its
> > circumference. =A0Pick a point outside the given
> > "two point" circle, and see if the circle one
> > that and the first two points contains all the
> > points. =A0If so, done.
>
> > Then you have a sequence of three-point circles
> > to consider until you find one that contains
> > all the points. =A0Here's where "pivoting" comes
> > into the picture. =A0We have three points A,B,C
> > that determine my current circle, and a point
> > D not contained by the circle. =A0Which point
> > A,B,C is to be replaced by D? =A0A simple way
> > to answer this is by trying all three and
> > comparing which has the smallest radius yet
> > still contains the replaced point. =A0IIRC 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). =A0The 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. =A0I think I've found a way to solve this using semi-definite
> programming.
>
> Call the known points (u_i, vi) with known radius ri. =A0Let (x,y) be the
> center of the spanning circle and r its radius. =A0The problem is then to
> minimize r subject to the conditions
>
> (*) =A0 =A0(ui - x)^2 + (vi - y)^2 <=3D (r-ri)^2, =A0 =A0r >=3D 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.) =A0These 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 =A0
>
> (1) =A0 =A0 <ei, ej> =3D Kronecker-delta (i,j).
>
> The only other unknowns are the (really!) unknown X =3D (x,y) and R =3D
> (r,0). =A0These satisfy the equations
>
> (2) =A0 =A0<R,e1> =3D r, =A0<R,e2> =3D 0. =A0
>
> Then the constraint (*) becomes
>
> (**) ui^2 + vi^2 - ri^2 <=3D r^2 - 2 r ri + 2 ui x + 2 vi y - (x^2 + y^2)
>
> =A0 =A0 =A0 =A0=3D <R,R> - 2ri <R,e1> + 2 ui <X,e1> + 2 vi <X,e2> - <X,X>
>
> The problem is to minimize r =3D <R,e1> subject to (**) and the
> additional constraints that
>
> =A0 =A0 =A0 =A0 =A0<X,e1> >=3D ri =A0 for all i.
>
> and that's why it's an SDP problem: =A0the 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. =A0
>
> I'm currently finishing a paper where I did a similar thing for
> intersecting spheres (closed balls) in R^N. =A0It turns out to be rather
> efficient. =A0THAT 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. =A0In particular, you would have to check
> whether
>
> =A0 =A0 =A0 <X,X> =3D <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. =A0(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.

regards, chip
```
 0
Reply Chip 11/21/2009 4:17:29 PM

```"Ronald Bruck" <bruck@math.usc.edu> wrote in message
news:201120090906363755%bruck@math.usc.edu...
> 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.

See publication lists at:
http://www.inf.ethz.ch/personal/fischerk/

A couple of implementations at:
http://miniball.sourceforge.net/
http://www.compgeom.com/meb/

--
Dave Eberly
http://www.geometrictools.com

```
 0
Reply Dave 11/22/2009 6:43:37 PM

```Andrew Tomazos pravi:
> 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:
>
>    { (x-a1)^2 + (y-b1)^2 ,
>      (x-a2)^2 + (y-b1)^2 ,
>      ... ,
>      (x-an)^2 + (y-bn)^2
>    }
>
> But how to do that?

It's very easy actually. I just wanted to ask a question related to
yours. You have a point set P with elements rp, you're looking for a
center rc of a minimum circle of radius r.

What I do in my algorithm is, I first derive an AABB of the point set
and then put a starting rc in the center of this AABB. That's my initial
guess. Then I use the hooke-jeeves algorithm (paper is online, but
better check Schaum's Operations Research for an easy explanation) to
minimize:

max({||rp-rc||^2}) with rc as the argument and all rps from P taken into
account. You'll get close to the minimum ball center this way and will
also get the radius (returned by the cost function). Even so, the welzl
algorithm will usually outdo this approach, due finite floating point
precision.

What I wanted to ask is:

Is the cost function max({||rp-rc||^2}) over all rp continuous?
Differentiable? Maybe one could get to the rc even faster using
derivatives? This approach works, I have working code.
```
 0
Reply keith 11/24/2009 1:48:32 AM

```keith wrote:
> What I do in my algorithm is, I first derive an AABB of the point set
> and then put a starting rc in the center of this AABB. That's my initial
> guess. Then I use the hooke-jeeves algorithm (paper is online, but
> better check Schaum's Operations Research for an easy explanation) to
> minimize:
>
> max({||rp-rc||^2}) with rc as the argument and all rps from P taken into
> account. You'll get close to the minimum ball center this way and will
> also get the radius (returned by the cost function). Even so, the welzl
> algorithm will usually outdo this approach, due finite floating point
> precision.
>
> What I wanted to ask is:
>
> Is the cost function max({||rp-rc||^2}) over all rp continuous?
> Differentiable? Maybe one could get to the rc even faster using
> derivatives? This approach works, I have working code.

Let P = {p_1, ..., p_m} subset R^n

The cost function is
f : R^n -> R: f(x) = max {||p - x||^2 : p in P}

To get an intuition for what this cost function looks like, consider the
problem in 1D (on real line) and visualize the graphs of the functions.
There the norm is the absolute value and each point in P generates a
quadratic curve around itself. The value of the cost function at x is
given by finding the maximum value on these curves at x. The 2D case can
similarly be visualized in 3D.

It should then intuitively be clear that the cost function is continuous
but not differentiable. The non-differentiable points are exactly those
at which the generator of the maximum value changes.

--
http://kaba.hilvi.org
```
 0
Reply Kaba 11/24/2009 10:57:14 AM

```> Let P = {p_1, ..., p_m} subset R^n
>
> The cost function is
> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
>
> To get an intuition for what this cost function looks like, consider the
> problem in 1D (on real line) and visualize the graphs of the functions.
> There the norm is the absolute value and each point in P generates a
> quadratic curve around itself. The value of the cost function at x is
> given by finding the maximum value on these curves at x. The 2D case can
> similarly be visualized in 3D.
>
> It should then intuitively be clear that the cost function is continuous
> but not differentiable. The non-differentiable points are exactly those
> at which the generator of the maximum value changes.

How do you know that the transfer between two generators is not smooth
enough for differentiability?
```
 0
Reply keith 11/24/2009 11:17:30 AM

```keith pravi:
>> Let P = {p_1, ..., p_m} subset R^n
>>
>> The cost function is
>> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
>>
>> To get an intuition for what this cost function looks like, consider the
>> problem in 1D (on real line) and visualize the graphs of the functions.
>> There the norm is the absolute value and each point in P generates a
>> quadratic curve around itself. The value of the cost function at x is
>> given by finding the maximum value on these curves at x. The 2D case can
>> similarly be visualized in 3D.
>>
>> It should then intuitively be clear that the cost function is continuous
>> but not differentiable. The non-differentiable points are exactly those
>> at which the generator of the maximum value changes.
>
> How do you know that the transfer between two generators is not smooth
> enough for differentiability?

Hmm, yeah, now I see it. It's like switching from one parabola to
another at a point. Too sharp a switch. Thanks for the info. That's why
on the safe side, I've used Hooke-Jeeves, which does not require
derivatives. The Ritter algorithm for the minimum sphere seems to be
much faster and mostly gives similar results.
```
 0
Reply keith 11/24/2009 11:27:14 AM

```> Let P = {p_1, ..., p_m} subset R^n
>
> The cost function is
> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}

I have a more difficult question now, Kaba (or anyone else). Is the
function f convex? Is it unimodal? The reason why I ask is, that I have
not fallen into any local minimum while searching for x yet.
```
 0
Reply keith 11/24/2009 1:41:48 PM

```keith wrote:
> > Let P = {p_1, ..., p_m} subset R^n
> >
> > The cost function is
> > f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
>
> I have a more difficult question now, Kaba (or anyone else). Is the
> function f convex? Is it unimodal? The reason why I ask is, that I have
> not fallen into any local minimum while searching for x yet.

With the same intuition as in the previous post, I say 'yes' and 'yes',
with no deeper proofs. I think the term unimodal is not applicable here
although I know that by that you mean 'there are no other minima'.

Let C = {(x, h) |  x in R^n, h >= f(x)}. Then in my mind R^n \ C looks
(at least when n = 1, 2) like a deep hole in ground whose walls and
floor are made of pieces of quadratics (of the same shape). Where the
pieces join there are more or less sharp corners. Convexity of f is a
consequence of the (used) quadratics being convex.

--
http://kaba.hilvi.org
```
 0
Reply Kaba 11/24/2009 4:41:27 PM

```Kaba pravi:
> keith wrote:
>>> Let P = {p_1, ..., p_m} subset R^n
>>>
>>> The cost function is
>>> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
> With the same intuition as in the previous post, I say 'yes' and 'yes',
> with no deeper proofs. I think the term unimodal is not applicable here
> although I know that by that you mean 'there are no other minima'.
>
> Let C = {(x, h) |  x in R^n, h >= f(x)}. Then in my mind R^n \ C looks
> (at least when n = 1, 2) like a deep hole in ground whose walls and
> floor are made of pieces of quadratics (of the same shape). Where the
> pieces join there are more or less sharp corners. Convexity of f is a
> consequence of the (used) quadratics being convex.

Still, you can make nonconvex functions by sticking quadratics together.
There must be some deeper intuition behind this.

The problem I have is that 1 or more (up to 4) points will domineer over
others. Say there is just 1 domineering point at first and you follow a
path minimizing f and 'catch' another domineering point. For a switch of
the quadratic the first and second domineering points must first make
for an equal f. You cannot move closer to the first, nor to the second
domineering point then, as you are then going to make f bigger either
way. You can only move on a path where the two points are equidistant (a
plane in 3D), eventually 'catching' more points, restricting movement
further. But if you are dealing with paths, to which certain points from
P are equidistant, then no 'switch' in the quadratics ever occurs.

What I am saying is that maybe a path exists from any point to the
global minimum, where no switch in the quadratics occurs and hence
derivatives are ok?
```
 0
Reply keith 11/25/2009 3:52:53 AM

```keith pravi:
> Kaba pravi:
>> keith wrote:
>>>> Let P = {p_1, ..., p_m} subset R^n
>>>>
>>>> The cost function is
>>>> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}

> What I am saying is that maybe a path exists from any point to the
> global minimum, where no switch in the quadratics occurs and hence
> derivatives are ok?

Well, I see now, that, there are infinitely many points (but not in the
1D line case you mention), where f is not differentiable.

Hence no derivatives.
```
 0
Reply keith 11/25/2009 4:27:08 AM

```keith wrote:
> Kaba pravi:
> > keith wrote:
> >>> Let P = {p_1, ..., p_m} subset R^n
> >>>
> >>> The cost function is
> >>> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
> > With the same intuition as in the previous post, I say 'yes' and 'yes',
> > with no deeper proofs. I think the term unimodal is not applicable here
> > although I know that by that you mean 'there are no other minima'.
> >
> > Let C = {(x, h) |  x in R^n, h >= f(x)}. Then in my mind R^n \ C looks
> > (at least when n = 1, 2) like a deep hole in ground whose walls and
> > floor are made of pieces of quadratics (of the same shape). Where the
> > pieces join there are more or less sharp corners. Convexity of f is a
> > consequence of the (used) quadratics being convex.
>
> Still, you can make nonconvex functions by sticking quadratics together.
> There must be some deeper intuition behind this.

Proof:

Let
f_j : R^n -> R: f_j(x) = ||x - p_j||^2
f = max {f_j}

If you accept that each f_j is convex, then:

(1 - t)f(x_1) + tf(x_2)
>= (1 - t)f_j(x_1) + tf_j(x_2)    (definition of f)
>= f_j((1 - t)x_1 + tx_2)         (convexity of f_j)

Because the previous holds for arbitrary j:

(1 - t)f(x_1) + tf(x_2)
>= max {f_j((1 - t)x_1 + tx_2)}
= f((1 - t)x_1 + tx_2)

Thus f is convex [].

> What I am saying is that maybe a path exists from any point to the
> global minimum, where no switch in the quadratics occurs and hence
> derivatives are ok?

Could be, I don't know for sure. Anyway, if there are at least two
points, f seems to be non-differentiable at the (global) minimum.

--
http://kaba.hilvi.org
```
 0
Reply Kaba 11/25/2009 9:03:33 AM

```Kaba pravi:
> keith wrote:
>> Kaba pravi:
>>> keith wrote:
>>>>> Let P = {p_1, ..., p_m} subset R^n
>>>>>
>>>>> The cost function is
>>>>> f : R^n -> R: f(x) = max {||p - x||^2 : p in P}
>
> Proof:
>
> Let
> f_j : R^n -> R: f_j(x) = ||x - p_j||^2
> f = max {f_j}
>
> If you accept that each f_j is convex, then:
>
> (1 - t)f(x_1) + tf(x_2)
>> = (1 - t)f_j(x_1) + tf_j(x_2)    (definition of f)
>> = f_j((1 - t)x_1 + tx_2)         (convexity of f_j)
>
> Because the previous holds for arbitrary j:
>
> (1 - t)f(x_1) + tf(x_2)
>> = max {f_j((1 - t)x_1 + tx_2)}
> = f((1 - t)x_1 + tx_2)
>
> Thus f is convex [].

I am no mathematician, but is convexity not determined by an inequality?
Furthermore, how can you be certain that the same f_j applies for both
x_1 and x_2?
```
 0
Reply keith 11/26/2009 3:37:32 AM

```keith wrote:
> > Thus f is convex [].
>
> I am no mathematician, but is convexity not determined by an inequality?

There are inequalities at the start of some rows. However, it seems
newsreaders interpret them as quotes. Reformatting:

Proof:

Let
f_j : R^n -> R: f_j(x) = ||x - p_j||^2
f = max {f_j}

If you accept that each f_j is convex, then:

(1 - t)f(x_1) + tf(x_2) >=      (definition of f)
(1 - t)f_j(x_1) + tf_j(x_2) >=  (convexity of f_j)
f_j((1 - t)x_1 + tx_2)

Because the previous holds for arbitrary j:

(1 - t)f(x_1) + tf(x_2) >=
max {f_j((1 - t)x_1 + tx_2)} =
f((1 - t)x_1 + tx_2)

Thus f is convex [].

> Furthermore, how can you be certain that the same f_j applies for both
> x_1 and x_2?

Perhaps you mean this step:

(1 - t)f(x_1) + tf(x_2) >=      (definition of f)
(1 - t)f_j(x_1) + tf_j(x_2)

Everything's positive, and f(x_i) >= f_j(x_i) by definition.

--
http://kaba.hilvi.org
```
 0
Reply Kaba 11/26/2009 7:22:06 AM

```keith wrote:
> > Thus f is convex [].
>
> I am no mathematician, but is convexity not determined by an inequality?

For some reason my first post didn't appear on the server I use so here
goes again to be sure.

There are inequalities at the start of some rows. However, it seems
newsreaders interpret them as quotes. Reformatting:

Proof:

Let
f_j : R^n -> R: f_j(x) = ||x - p_j||^2
f = max {f_j}

If you accept that each f_j is convex, then:

(1 - t)f(x_1) + tf(x_2) >=      (definition of f)
(1 - t)f_j(x_1) + tf_j(x_2) >=  (convexity of f_j)
f_j((1 - t)x_1 + tx_2)

Because the previous holds for arbitrary j:

(1 - t)f(x_1) + tf(x_2) >=
max {f_j((1 - t)x_1 + tx_2)} =
f((1 - t)x_1 + tx_2)

Thus f is convex [].

> Furthermore, how can you be certain that the same f_j applies for both
> x_1 and x_2?

Perhaps you mean this step:

(1 - t)f(x_1) + tf(x_2) >=      (definition of f)
(1 - t)f_j(x_1) + tf_j(x_2)

Everything's positive, and f(x_i) >= f_j(x_i) by definition.

--
http://kaba.hilvi.org
```
 0
Reply Kaba 11/26/2009 8:30:21 AM

37 Replies
482 Views

Similar Articles

12/5/2013 5:07:30 AM
page loaded in 91897 ms. (0)