[Date Index]
[Thread Index]
[Author Index]
Re: FindMinimum and the minimum-radius circle
Fred,
nice analytical approach, for this 'easy' case. The advantage of a general
optimization approach is that one can use it to solve many other (incl.
non-convex) packing models: I mentioned such in previous notes.
Regards,
Janos Pinter
At 07:34 AM 8/23/2004, Fred Simons wrote:
>The recent messages about the problem of finding the minimum radius circle
>are actually a discussion on the numerical aspects of the problem. The
>following remark is a little bit outside that scope.
>
>It is possible to construct that circle directly. I have to admit that I did
>not follow this thread very carefully, so if someone else already gave a
>similar construction, I strongly apologize.
>
>The idea is that the smallest circle is a circle that passes through three
>points or passes through two diametrical points (that has been remarked). A
>little bit more can be said: when the smallest circle passes through three
>points, then the center of the circle must be inside the triangle. So the
>construction runs as follows. First construct a circle that contains all
>points and passes through one point. Then move the center of the circle in
>the direction of that point until it passes through a second point. When
>these points are diametric, we are ready. Otherwise, move the center of the
>circle to the connecting line until it passes through a third point. Then
>test. If the center of the circle is outside the triangle, move it in the
>direction of the largest side of the triangle taking care that all points
>remain inside the circle, and so on. Here is an implementation:
>
>smallestcircle[points_] :=
>Block[{m, p1, p2, p3, v, t, t0, pts = points},
>m = Mean[points];
>p1 = p2 = p3 = points[[Ordering[points, -1,
>(#1 - m) . (#1 - m) < (#2 - m) . (#2 - m) & ][[1]]]];
>While[Length[Union[{p1, p2, p3}]] < 3 ||
>(p1 + p2)/2 == m || (p1 - p2) . (p1 - p2) >
>(p1 - p3) . (p1 - p3) + (p2 - p3) .
>(p2 - p3),
>v = (p1 + p2)/2 - m; t = 1; p = p3;
>pts =
>Reap[Scan[If[v . (#1 - p1) < 0,
>Sow[#1]; t0 = ((m - #1) . (m - #1) -
>(m - p1) . (m - p1))/(2*
>v . (#1 - p1)); If[t0 < t,
>t = t0; p = #1]] & , pts]][[2]];
>If[pts == {}, Break[], pts = pts[[1]]];
>m = m + t*v; p3 = p; {p1, p2, p3} =
>If[(p3 - p1) . (p3 - p1) >= (p2 - p1) .
>(p2 - p1), {p1, p3, p2},
>{p3, p2, p1}]];
>Circle[m, Norm[m - p1]]]
>
>For exact coordinates we find the exact circle. This function is faster than
>the numerical ones:
>
>In[561]:=
>SeedRandom[1];
>points = Partition[Table[Random[], {1000}], 2];
>Timing[NMinimize[
>Sqrt[Max[((x - #1[[1]])^2 + (y - #1[[2]])^
>2 & ) /@ points]], {x, y}]]
>Timing[smallestcircle[points]]
>
>Out[563]=
>{4.625*Second, {0.6628153793262672,
>{x -> 0.48683054240909296,
>y -> 0.46145830394871523}}}
>Out[564]=
>{0.14000000000000057*Second,
>Circle[{0.48684175891608683,
>0.46146943938871915}, 0.6628150360165743]}
>
>
>Fred Simons
>Eindhoven University of Technology
Prev by Date:
**Re: Re: Comparison of Mathematica on Various Computers**
Next by Date:
**Re: Re: Re: Re: Re: Re: FindMinimum and the minimum-radius circle**
Previous by thread:
**Re: Re: Re: Re: Re: FindMinimum and the minimum-radius circle**
Next by thread:
**Re: Re: Re: Re: Re: Re: FindMinimum and the minimum-radius circle**
| |