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/