Smallest sphere problem:final solution-again
- To: mathgroup at smc.vnet.net
- Subject: [mg16648] Smallest sphere problem:final solution-again
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Fri, 19 Mar 1999 12:54:01 -0500
- Sender: owner-wri-mathgroup at wolfram.com
I was careless in describing my "final solution" to the smallest sphere problem in the 3 D case (the last remark about "three points on the diameter of a sphere" does not make sense!). Here is what I think is the final and correct (I hope!) version: Suppose we are given a finite collection of points in 3 space. Let S be a spehre containing all these points and having the smallest possible radius. I claim that the sphere must have one of the following properties: 1) it contains 4 points non-coplanar points of th eset or 2) it contains three non-colinear points of the set on a great circle or 3) it contains two distinct points of the set as end points of a diameter The reason is that if all these conditions fail the spehre cannot be a minimal one. It can be replaced by a slightly smaller sphere. So the algorithm is: find all linearly independent 4-tupes of points and the spheres they determine. Find all linearly independents triples of points, the cirles they determine and the spheres having these circles as great circles. Find all pairs of distinct points and the spheres having these points as diameters. Check which of these spheres contaian all the points of the set. Then chose from among them the one of the least radius. The algoritm is much worse than I thought at first but still seems to work in polynomial time (?) Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp/ http://eri2.tuins.ac.jp/