MathGroup Archive 1999

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

Search the Archive

Re: Problem: Smallest sphere including all 3D points

  • To: mathgroup at smc.vnet.net
  • Subject: [mg16529] Re: [mg16471] Problem: Smallest sphere including all 3D points
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Tue, 16 Mar 1999 04:00:06 -0500
  • Sender: owner-wri-mathgroup at wolfram.com

Just a short addendum to my earlier message. I ignored the possibility
that some of the points may be in non-generic positions, e.g. three
points in a line or four points on a plane. These cases can be eliminated
by checking the determinants of the corresponding matrices or, better,
one can use the option AllPoints->False in ConvexHull. The second problem
is that I forgot that Mathematica's ConvexHull function is defined only
for sets of points in 2D. One does not really need this for the algorithm
below to work but it will of course become much less efficient as one
will need to test all choices of four points out of the given set.


On Sat, Mar 13, 1999, Barthelet, Luc <lucb at ea.com> 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!)
>	 
>	 
At this moment all I can do is to describe a fairly obvious algoritm to
solve this problem. It is not difficult to implement in Mathematica but
to do so would be a rather long and tedious task for me. Since I have
never before considered this problem (or any similar one) and never read
anything in this area I strongly suspect that there may exist a better
and more efficient one, which is another reason not to waste time on an
implementation at this stage.

Okay, now the algorithm. Let's first consider the analogous two
dimensional prooblem, because it is slightly easier to visualize. In
other words, we have a set of points in the plane and want to find a
circle of the smallest radius containing all the points. The first step
is, as you rightly observed, to take the convex hull, which can be done
by means of a function in the package DiscreteMath`ComputationalGeometry`
. Let us assume that this consists of more than two points, otherwise the
problem is trivial.

Now, clearly a circle of the smalles radius with this property does
exist. The key observation is that any such circle must pass through at
least three points of our set (convex hull). The reason is this: if a
circle passes through only two points (or one point, or no points at all)
and contains the rest than it can be replaced by a slightly smaller
circle with the same property. This is intuitively obvious and can easily
be proved. This immediately suggests the algorithm. We consider all
possible choices of three points from our convex hull. For each set of
such three points (a triangle) we find the circumscribed circle. This can
esily be done in Mathematica using the Solve function to solve three
quadratic equations with three unknowns (coordinates of the center and
the radius). Next, we inspect all the circles to find those which have
the property that they contain all the points of the set. Again, this is
easy to implement in Mathematica (you just substitute the coordinates of
the points into the equation of each circle and check the sign). There
must be at least one circle which contains all the points (including the
three lying on the circle). If there are more than one such circle we
choose the one with the smallest radius.

Now, it is obvious what to do in three dimensions. The first step as
before is to take the convex hull. Next, any four points in the convex
hull determine a sphere, and as before the minimal sphere must pass
through four points of the hull. We take all possible choices of four
points, find the spheres they determine, check which ones contain all the
other points and finally choose the sphere of the smallest radius.


Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp/
http://eri2.tuins.ac.jp/



  • Prev by Date: Re: Problem: Smallest sphere including all 3D points
  • Next by Date: Re: Problem: Smallest sphere including all 3D points
  • Previous by thread: Re: Problem: Smallest sphere including all 3D points
  • Next by thread: Re: Problem: Smallest sphere including all 3D points