Re: Re: Smalest enclosing circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50102] Re: [mg50068] Re: [mg50062] Smalest enclosing circle
- From: DrBob <drbob at bigfoot.com>
- Date: Sun, 15 Aug 2004 03:14:28 -0400 (EDT)
- References: <NDBBJGNHKLMPLILOIPPOGEHEECAA.djmp@earthlink.net> <200408140550.BAA15268@smc.vnet.net> <49314.69.22.221.187.1092495441.squirrel@webmail.wolfram.com>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Unfortunately, FindMinimum isn't finding the optimum much of the time. I squelched the error message thinking it was a precision issue, and I didn't need to be precise; but it's worse than that. I'll look at it again later.
Bobby
On Sat, 14 Aug 2004 09:57:21 -0500 (CDT), <danl at wolfram.com> wrote:
>>> You know, it was not immediately obvious to me that two points should be
>>> on
>>> the circle.
>>
>> If there's only one point on a circle that encloses all the points, the
>> radius can shrink while moving the center directly toward that point. That
>> can continue smoothly until the circle touches another point. If the
>> initial point was not well chosen, the result isn't necessarily optimal,
>> but it's better than the initial circle that goes through only one point.
>>
>> I see no way to take advantage of this, but we CAN use ConvexHull to do
>> some of the work (if that happens to be more efficient):
>>
>> Needs["DrawGraphics`DrawingMaster`"]
>> Needs["DiscreteMath`ComputationalGeometry`"]
>> data = RandomArray[NormalDistribution[0, 1], {12, 2}];
>> hull = data[[ConvexHull@data]];
>> sq = #.# &;
>> radius[x_?NumericQ, y_?NumericQ] := Sqrt@Max[sq[{x, y} - #] & /@ hull]
>> Off[FindMinimum::"lstol"]
>> soln = FindMinimum[radius[x, y], {x, 0}, {y, 0}, WorkingPrecision -> 20]
>> pt = {x, y} /. Last@soln;
>> r = First@soln;
>> Draw2D[{PointSize[0.02], Point /@ data,
>> Red, Point@pt, Circle[pt, r], Blue, Point /@ hull}, AspectRatio ->
>> Automatic]
>>
>> Nice picture, huh?
>>
>> Two or more "hull" points will be on the circle each time. I see three on
>> the circle fairly often, in fact; but I'm sure that's an optical
>> conclusion.
>>
>> Bobby
>> [...]
>
> Generically I'd expect three points on the minimal enclosing circle (the
> exceptional case, as Andrzej notes, being when two are on ends of a
> diameter chord). From a computational complexity viewpoint one can use
> ConvexHull to reduce the number of points under consideration.
>
> After that, so far as I can tell the best way to find the circle is as you
> do. This is because it's a convex optimization problem, so the local
> minimizer found by FindMinimum is actually a global one.
>
> Daniel
>
>
>
>
--
DrBob at bigfoot.com
www.eclecticdreams.net
- References:
- Re: Smalest enclosing circle
- From: DrBob <drbob@bigfoot.com>
- Re: Smalest enclosing circle