Re: Smallest enclosing circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50130] Re: Smallest enclosing circle
- From: "Dr. Wolfgang Hintze" <weh at snafu.de>
- Date: Mon, 16 Aug 2004 06:45:40 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Over the weekend I had no contact to the internet - but had a nice time
trying to solve this marvellous problem - which I couldn't. I'm
nevertheless posting what I did without first reading all other
messages. Hence you can judge beforehand if it is worth reading further...
Here are my (preliminary) results:
1) Using ConvexHull of the package DiscreteMath`ComputationalGeometry`
the problem can be traced back to finding the smallest enclosing circle
(SEC) for a convex (irregular) polygon. This (at least) can reduce the
number of points to be considered.
BTW: this packages seems to have no solution to our problem.
2) Scaling to lower limit
Let A and B be two points which have the maximum possible distance dMax
of all pairs of points.
We draw a circle through A and B with diameter equal to the distance
between A and B.
This circle is called the minimum circle. We normalize the problem so
that the minimum circle has radis unity.
It is obvious then that the any enclosing circle must have at least
radius unity.
3) "Worst" arragement of points
What is the "worst" arrangement of points? This is by definition an
arragement which requires the greatest SEC. A related question ist: what
is the radius rMax of the SEC of the worst arragement as measured in
units of dMax?
My preliminary results show that a lower limit for rMax is equal to
2/Sqrt(3) = 1.1547... This is the case when three points form an
equilateral triangle, the points A and B (as above) and a point E having
distance unity from A and from B.
4) Picture of the situation (might be of interest to others as well)
This can be generated using the following command lines:
In[15]:=
Off[General::spell];
In[1]:=
p2g[x_] := Graphics[Point[x]];
In[22]:=
pA = {-1, 0}; gpA = p2g[pA]; gTextA = Graphics[Text["A", pA - {0.1, 0}]];
In[23]:=
pB = {1, 0}; gpB = p2g[pB]; gTextB = Graphics[Text["B", pB + {0.1, 0}]];
In[24]:=
pM = (pA + pB)/2; gpM = p2g[pM]; gTextM = Graphics[Text["M", pM - {0,
0.15}]];
In[25]:=
pC = {-0.3, 0.6}; gpC = p2g[pC]; gTextC = Graphics[Text["C", pC - {0.1,
0}]];
In[26]:=
pD = {0.2, -0.6}; gpD = p2g[pD]; gTextD = Graphics[Text["D", pD - {0.1,
0}]];
In[27]:=
pE = {0, Sqrt[3]}; gpE = p2g[pE]; gTextE =
Graphics[Text["E", pE + {0, 0.15}]];
In[28]:=
pF = {0, -Sqrt[3]}; gpF = p2g[pF]; gTextF =
Graphics[Text["F", pF - {0, 0.15}]];
In[29]:=
pG = {-0.1, 1.3}; gpG = p2g[pG]; gTextG = Graphics[Text["G", pG - {0.1,
0}]];
In[30]:=
pH = {-0.2, -1.4}; gpH = p2g[pH]; gTextH = Graphics[Text["H", pH - {0.1,
0}]];
In[31]:=
pR = {Sqrt[3] - 1, 1}; gpR = p2g[pR]; gTextR =
Graphics[Text["R", pR + {0.1, 0}]];
In[32]:=
pS = {Sqrt[3] - 1, -1}; gpS = p2g[pS]; gTextS =
Graphics[Text["S", pS + {0.1, 0}]];
In[33]:=
gLAB = Graphics[Line[{pA, pB}]];
In[34]:=
picMinCircle = Graphics[Circle[pM, 1]];
In[35]:=
eps = 0.3;
In[36]:=
gBogenUmA = Graphics[Circle[pA, 2, {-\[Pi]/2 + eps, \[Pi]/2 - eps}]];
gBogenUmB = Graphics[Circle[pB, 2, {-3\[Pi]/2 + eps, -\[Pi]/2 - eps}]];
In[38]:=
ps = 0.03;
Show[Graphics[PointSize[ps]], gpA, gpB, gpM, gLAB, gpC, gpD, gpE, gpF,
gpG, gpH, gpR, gpS, gTextA, gTextB, gTextM, gTextC,
gTextD, gTextE, gTextF, gTextG, gTextH, gTextR, gTextS,
picMinCircle, gBogenUmA, gBogenUmB, AspectRatio -> Automatic,
PlotRange -> All];
Regards,
Wolfgang
Steve Gray wrote:
> Given n points in the plane, I want to find the smallest
> enclosing circle. Does anyone have Mathematica code to do this?
> I will be grateful for any tips.
>
> Steve Gray
>
>