Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!mit-amt!turk@media-lab.media.mit.edu From: turk@media-lab.media.mit.edu (Matthew Turk) Newsgroups: comp.graphics Subject: Re: Ray Traced Bounding Spheres Summary: Nope...! Message-ID: <3781@mit-amt> Date: 15 May 89 13:19:47 GMT References: <17241@versatc.UUCP> <17249@versatc.UUCP> <8411@phoenix.Princeton.EDU> Sender: turk@mit-amt Reply-To: turk@media-lab.media.mit.edu Organization: MIT Media Lab Lines: 61 In-reply-to: sarrel@galley.cis.ohio-state.edu's message of 15 May 89 02:39:48 GMT 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. > Yes, but unfortunately it's *not* guaranteed to work! > The reason that this algorithm works is as follows. We know that > there are two points such that the distance between them is greater > than the distance between any other two points, call them p2 and p3 > (as above). Call the line between p2 and p3 d1 (for diameter). Call > the point midway along d1 c1 (for center). Put a plane perpendicular > to d1 through the point c1. This divides the points into two sets. > For all the points on one side of the plane, point p2 is the farthest > away and for all the points on the other side, p3 is farthest away. > Now, we can see that step two above finds one of the points that > define the bounding sphere and that step three must find the other. > QED (for an informal argument). > This reasoning is incorrect. Your p2 and p3 are the points farthest away on each side of a plane -- they are not related to the bounding sphere. As a counter example to your algorithm, note this figure: | 3 point 1 - (0,0) | 2 - (10,0) | 3 - (0,9) | 4 - (0,-8) | -------------1------------2-- | | | 4 | Step (1) - I'll pick p1, at (0,0). Step (2) - the farthest point is p2, at (10,0). Step (3) - the farthest from p2 is p3, at (0,9). Step (4) - the minimum sphere defined by p2 and p3 is centered at (5,4.5), and has a radius of 6.727. But since the distance between the sphere's center and p4(0,-8) is 13.463, p4 is not in the minimum sphere. Better luck next time! Matthew Turk Vision Science Group, MIT Media Lab turk@media-lab.media.mit.edu