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

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 ,

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

"Andrew Tomazos" <andrew@tomazos.com> wrote in message 
news:6bc4f385-4b1d-4c1e-b558-37479c4dad9f@k17g2000yqh.googlegroups.com...
> 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 

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

regards, chip

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

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

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

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

In 
<6bc4f385-4b1d-4c1e-b558-37479c4dad9f@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

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

Megiddo's Linear-Time Algorithm?
--
Regards,
Casey

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-
37479c4dad9f@k17g2000yqh.googlegroups.com>, andrew@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.

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

>In article <6bc4f385-4b1d-4c1e-b558-
>37479c4dad9f@k17g2000yqh.googlegroups.com>, andrew@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.

People never seem to read the FAQ's anymore, they just FAQ off!

--
Regards,
Casey

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!

n 
<6bc4f385-4b1d-4c1e-b558-37479c4dad9f@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.

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

In article
<5b980a85-0f88-440e-aabc-a0faf1345ca9@w19g2000yqk.googlegroups.com>,
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
additional constraints that

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

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

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

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

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

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

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

-- Ron Bruck

In article
<5b980a85-0f88-440e-aabc-a0faf1345ca9@w19g2000yqk.googlegroups.com>,
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
additional constraints that

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

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

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

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

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

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

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

-- Ron Bruck

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

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

> In article
> <5b980a85-0f88-440e-aabc-a0faf1345ca9@w19g2000yqk.googlegroups.com>,
> 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

On Nov 18, 3:46=A0am, Ronald Bruck <br...@math.usc.edu> wrote:
> In article
> <5b980a85-0f88-440e-aabc-a0faf1345...@w19g2000yqk.googlegroups.com>,
>
>
>
> 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

"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
 

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.

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

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

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.

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

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

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?

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.

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

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?

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

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