MathGroup Archive 1999

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

Search the Archive

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/




  • Prev by Date: RE: Problem: Smallest sphere including all 3D points
  • Next by Date: RE: Integration using "shortcut keys"
  • Previous by thread: Re: Viewpoint Scaling
  • Next by thread: combinations