Finding a minimum bounding sphere for a frustum

Question

I have a frustum (truncated pyramid) and I need to compute a bounding sphere for this frustum that's as small as possible. I can choose the centre to be right in the centre of the frustum and the radius be the distance to one of the "far" corners, but that usually leaves quite a lot of slack around the narrow end of the frustum

This seems like simple geometry, but I can't seem to figure it out. Any ideas?

Answer 1

The way to do this is to find a sphere that fits 4 points on your frustum. If this is a proper frustum (a truncated pyramid - my bad I was assuming a cylindrical fristum), then you get two points from opposite corners of the top quad, and the other two from the bottom quad, out of phase with the top two. Then use this to get your sphere.

Answer 2

There are several algorithms and implementations out there for this problem (see also this post).

• For 2D and 3D, Gärtner's implementation is probably the fastest.

• For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

• For very, very high dimensions, core-set (approximation) algorithms will be faster.

In your particular application, you may want to try either of the first two algorithms. Both run in O(n) with a very small constant and are numerically stable.