Finding a minimum bounding sphere for a frustum I have a frustum (truncated pyramid defined by six planes) and I need to compute a bounding sphere for this frustum that's as small as possible.
I can choose the centre of the sphere to be right in the centre of the frustum and the radius be the distance to one of the "far" corners (the base of the pyramid), but that usually leaves quite a lot of slack around the narrow end of the frustum. There must be a better way!
This seems like simple geometry, but I can't seem to figure it out. Any ideas?
 A: I knew the answer was simple, but I just couldn't think of it, so I went and looked it up in some old course notes from a computational geometry course. This elegant solution is apparently due to Emo Welzl and finds the smallest enclosing ball of any number of points in any dimensionality. It should work nicely for you. Here it is, paraphrased in pseudo-Haskell from "Backwards Analysis of Randomized Geometric Algorithms," by Raimund Seidel: 

minidisk :: ({Point}, {Point}) -> Ball
minidisk({}, C) = primitive_ball(C)
minidisk(T, C)  = 
    let p  = uniformly_random_point(T)
        T' = T\{p}
        B' = minidisk(T', C)
    in 
        if contains(B', p) then B' 
        else minidisk(T', union(C, {p}))

Here T and C are finite sets. primitive_ball(C), as one would guess, is the ball whose center and radius are the circumcenter and circumradius of the points in C. minidisk(T, C) finds the smallest ball enclosing all the points of T and having all the points of C on its boundary. What you want is thus minidisk(T, {}), where T is the set of eight vertices of the frustum. 
(Note that p is chosen uniformly at random to obtain a good expected running time for large T; you can actually choose p from T however you want without sacrificing correctness. In fact, in your case, I wouldn't be surprised if there were some particular ordering of the vertices that results in better performance. Experiment!)
