Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
That should be frustrum. Also, could you specify if the pyramid you're truncating has square base and is symmetric? If so then your problem simplifies. –  Yemon Choi Feb 3 '10 at 19:45
    
It's not square no, however I know that one of the sides will always be longer than the other. I think I've got it, actually. Simplifying it into 2D on the longest axis, and stipulating that the distance to the far vertex on the base and the far vertex on the truncated top should be equal (i.e. the bounding sphere touches the outside vertices), and the maths just kind of works out from there I think. I got that the distance from the base should be (Wn^s + Wf^2 +x^2)/2x, where Wn is the half-width of the narrow side, Wf is the half-width of the fat end, and x is distance from base to top. –  Bob Feb 3 '10 at 19:55
7  
This problem seems like it would be better suited for one of the other sites mentioned in the FAQ. Anyway, whether it's symmetric or not, the smallest sphere should pass through some vertices of the object, so the center is the same distance from several vertices. The locus of points equidistant from two points is a plane defined by one linear equation. If there are 2 vertices, the sphere's center must be the midpoint of the line segment connecting them. If 3, the locus is a line which intersects the vertices' plane in one point. If there are 4 non-coplanar vertices, the locus is one point. –  Douglas Zare Feb 3 '10 at 19:56
    
I reverted an earlier edit, noting that there is only one 'r' in 'frustum' (confirmed using multiple sources). –  Darsh Ranjan Feb 4 '10 at 1:35
    
Ah, that was my fault, Darsh. Thanks for the correction –  Yemon Choi Feb 4 '10 at 2:25
add comment

1 Answer 1

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!)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.