Re: Re: Problem: Smallest sphere including all 3D points
- To: mathgroup at smc.vnet.net
- Subject: [mg16615] Re: [mg16556] Re: [mg16471] Problem: Smallest sphere including all 3D points
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Fri, 19 Mar 1999 12:53:46 -0500
- Sender: owner-wri-mathgroup at wolfram.com
Just atiny correction to my last message: the example I meant you to look
at was:
In[1]:=
l={{-1,0,0},{0,1,0},{1,0,0}};
In[2]:=
smallestSphere[l]
Out[2]=
1 Sqrt[10]
{{0, -, 0}, --------}
3 3
In[3]:=
l={{-1,0,0},{0,1,0},{1,0,0},{0.9,0,0}};
In[4]:=
smallestSphere[l]
Out[4]=
{{0.225, 0.25, 0.}, 1.25025}
The smallest sphere should of course be the same (These points are
coplanar and the extra point in fact lies within the convex hull of the
others, but one can easily construct examples without these properties).
-------------------------------------------------------------------
Jurgen,
It seems to me that your method (least squares) cannot work in this case.
The reason is that the least squares method computes a kind of "mean",
and not the center of the minimum circle which Luc wanted. To see this
consider the following argument. Let us start with a configuration of
points and suppose that we find the center using the least squares
method. Fix one of the points in the configuration and start adding
additional points, very close to this point. One can do so in a way that
will not change the position of the minimal circle in Luc's sense.
However, it is clear that the postion of the center computed according to
the least squares method will start shifting towards the fixed point, as
it "weight" increases. You can see this even more clearly by considering
the limiting case of just two points, but one counted several times (one
can think of this case as two prticles, one heavier than the other). The
center of the least circe will be still the midpoint, but the center
given by the least squares method will be closer to the heavier particle.
You can easily test this:
In[60]:=
l={{1,0,0},{0,1,0},{0,0,1}};
In[61]:=
smallestSphere[l]
Out[61]=
1 1 1 2
{{-, -, -}, Sqrt[-]}
3 3 3 3
In[62]:=
l={{1,0,0},{0,1,0},{0,0,1},{0,0,0.9}};
In[63]:=
smallestSphere[l]
Out[63]=
{{0.25, 0.25, 0.475}, 0.922293}
Andrzej
On Tue, Mar 16, 1999, Jurgen Tischer <jtischer at col2.telecom.com.co> wrote:
>Luc,
>use the force, in this case minimum squares:
>If li is your list of points, then
>
>smallestSphere[li_] :=
> Module[{x, y, z, r},
> {x, y, z} = {x, y, z} /.
> First[Solve[(D[Plus @@ (With[{a = #1 - {x, y, z}}, a . a] & ) /@ li,
>#1] & ) /@ {x, y, z} == 0]];
> r = Max[(With[{a = #1 - {x, y, z}}, Sqrt[a . a]] & ) /@ li];
> {{x, y, z}, r}]
>
>Jurgen
>
>"Barthelet, Luc" wrote:
>>
>>
>> I was just asked by a friend how to find the smallest sphere that
>> would include all points from a set of 3D points.
>> It feels like finding a 3D convex hull and then finding the best
sphere (??)
>> I would appreciate any complete solution or best set of pointers...
>>
>> Thank you,
>>
>> Luc Barthelet
>> General manager, Maxis
>> http://www.simcity.com <http://www.simcity.com> (we are
>> #1!)
>>
>>
>
>
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp/
http://eri2.tuins.ac.jp/