Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!shadooby!accuvax.nwu.edu!tank!eecae!cps3xx!flynn
From: flynn@pixel.cps.msu.edu (Patrick J. Flynn)
Newsgroups: comp.graphics
Subject: Re: Ray Traced Bounding Spheres
Keywords: Ray trace, bounding volumes, intersection
Message-ID: <2942@cps3xx.UUCP>
Date: 11 May 89 11:46:51 GMT
References: <17241@versatc.UUCP>
Sender: usenet@cps3xx.UUCP
Reply-To: flynn@pixel.cps.msu.edu (Patrick J. Flynn)
Organization: Bag O' Pixels, Ltd.
Lines: 21

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?  If not
>minumum, at least "small"?  Certainly it should
>be tighter than the sphere which encloses the
>minimum bounding box.

This is a 3D generalization of the `smallest enclosing circle' problem, which
is covered in Preparata and Shamos' book on computational geometry (see pp.
248ff.). In 2D, you can find a smallest bounding circle for n points in
n log n time.  I don't know how that scales to 3D.

>I have a feeling the solution is iterative.

Hmm, it shouldn't be.  It's a discrete problem.  See P&S for a discussion
of the (mis-)formulation of the bounding-circle problem as a continuous problem.
------------------------------------------------------------------------------
Pat Flynn, CS, Mich. State U | "In your heart, you know it's biscuit shaped."
flynn@cps.msu.edu            |                                    -Me
(517) 353-4638               |