MathGroup Archive 1999

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

Search the Archive

Smallest sphere problem:final solution?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg16637] Smallest sphere problem:final solution?
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Fri, 19 Mar 1999 12:53:56 -0500
  • Sender: owner-wri-mathgroup at wolfram.com

Hartmut Wolf has pointed out that my solution of the smallest sphere
problem is wrong. I quote from his message:

>To show that this is wrong, look at the appended notebook. You see a red
>line, where we consinder the "third" point moving on. The other points
>are considered fixed for that inspection. Two circles are shown. Only
>when the "third" point is between the two positions shown, then your
>conjecture is true. When the "viewing angle" at the third point to the
>other points is greater than 90 it can't lie on the peripheral of the
>smallest circle. Same applies to the right point at the basis, when the
>"third point" has moved farther out.

(anybody interested in this can receive the notebook from me, but
actually drawing this situation on paper should suffice)

My mistake was this (in two dimensional case). I argued as follows.
Suppose there is a minimal circle which does not pass through three
points. Than we can deform it slightly, while making it pass through
these two points, and get a smaller circle. But of course this is not
true if these points lie on the diiameter of the circle. Any deformation
will then produce a larger circle. Thus the argument fails.
However, it can be modified and the modified version seems to be O.K.
Here it is:

We first consider all pairs of points from our set and all circles which
have any such pair as a diameter. We then proceed as before, in other
words, we consider all cirlces corcumscribed on three points out of our
set. We then look for cirlces containing all the points and then take the
smallest.

The argument is now as follows. Consider the minimum circle. If it passes
only through one point of our set we can certainly make it smaller
without it leaving this point. If it passes through two points of our
set, which are not on its diameter, we can make it slightly smaller.
Hence the minimal circle must either pass through three points or have
two points on its diameter.

In the 3D case we proceed analogously. Again, we must include not only
all spheres circumscribed on tetrahedra (for points) but also all spheres
which have any three points on their diameter. This of course will make
the algorithm more complex.



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




  • Prev by Date: Re: need a hand ordering functions
  • Next by Date: Viewpoint Scaling
  • Previous by thread: Re: Plotting Points
  • Next by thread: Viewpoint Scaling