Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!leah!rpi!rpics!guilford From: guilford@rpics (Jim Guilford) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Message-ID: <4057@rpi.edu> Date: 15 May 89 14:29:31 GMT References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> Sender: usenet@rpi.edu Reply-To: guilford@turing.cs.rpi.edu (Jim Guilford) Organization: RPI CS Dept. Lines: 47 In article <17241@versatc.UUCP>, ritter@versatc.UUCP (Jack Ritter) writes: > Given a cluster of points in 3 space, is there > a good method for finding the minumum radius > sphere which encloses all the points? In article sarrel@galley.cis.ohio-state.edu (Marc Sarrel) writes: >Here is my solution, which I _know_ to be linear in the number of >points. > >Problem: >Given a set of points in three space, find the two that are farthest >apart and use them to define a minimum bounding sphere. > >Solution: >1) Pick a point, any point, call it p1 >2) Find the farthest point from p1, call it p2. >3) Find the farthest point from p2, call it p3. >4) Use p2, p3 and the distance between them to define your minimum > bounding sphere. > >That's it. It is guaranteed to be linear, too. I'm not sure if your problem statement is actually the problem statement, or a partial solution statement as well, but if you are trying to solve the earlier problem (bounding sphere of n points), then I'm afraid that doesn't work. Consider three points in a plane arranged as an equilateral triangle: (1,sqrt(3)) A / \ / \ / \ / \ B---------C (0,0) (2,0) If you (for simplicity) pick B and C as the farthest points, and then center a sphere at (1,0) with a radius of 1 (so that it just encloses B and C), then A will be outside the sphere. In general, the center will not lie on the line between any two points. Consider also the case of four points arranged in a tetrahedron. --JimG guilford@turing.cs.rpi.edu