Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: New user: Abs[] problem
  • Next by Date: Re: Reduce/Solve
  • Previous by thread: My regrets ...
  • Next by thread: Magnetica