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/