Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!deimos.cis.ksu.edu!rutgers!njin!princeton!phoenix!mplevine From: mplevine@phoenix.Princeton.EDU (Marshall P. Levine) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Summary: My algorithm works! Fast! Keywords: ray, trace, sphere, minimum, linear Message-ID: <8495@phoenix.Princeton.EDU> Date: 17 May 89 19:18:37 GMT Reply-To: mplevine@phoenix.Princeton.EDU (Marshall P. Levine) Organization: Computer Science Department, Princeton University Lines: 31 In article sarrel@galley.cis.ohio-state.edu (Marc Sarrel) writes: >Well, I don't argue that the posted algorithm works (although I'm not >sure about its linearity), I don't think that it answers the question >exactly. Actually, Marc, I carefully analyzed my program. It finds the minimum spanning sphere on the average at a linear time. It is possible that its time will not be spectacular (given a really bad distribution of points) but it should never be n^2. I don't think most people who are posting replies to my program understand what I did. My algorithm, given a space of randomly distributed points, will find the sphere of minimum radius, centered on ANY POINT IN THE SPACE, that contains NUMINSPHERE other points. The key here is that the sphere can be centered on ANY POINT IN THE SPACE. Most of the ideas that I have seen posted involve comparing every point against every other point. That is guaranteed to be n^2. In fact, my BRUTEFORCE algorithm included in my posting will do precisely that. If you are skeptical about the accuracy of my algo, compile the source youself. I wrote it in standard pascal, and you should have no problems compiling it. As for speed tweeking, obviously the square-root function is unnecessary. I am not stupid. While my algos are sorting the distances that they consider, they do not need the square roots. The only square root that needs to be calculated is the square root of the final number produced by the algos, which will be the answer to the problem. I included the square-root functions because I figured that it would be easier for people to understand what I did. Once again, if there are any questions, feel free to contact me. Good luck. Best wishes, Marshall Levine mplevine@phoenix.princeton.edu