Bounding box of spherical sector (cone-sphere intersection)

Question

Given a spherical segment (its radius, direction and angle), how do I compute its axis-aligned bounding box in a easiest way?

Note that I'm interested in arbitrarily oriented segment, while the box must be axis-aligned. Tight oriented bounding box is trivial to compute.

The problem can be simplified to a bounding box of a spherical cap, but I couldn't find algorithm for that either.

Answer 1

For simplicity, assume that we translate and scale the coordinate system so that the center is at (0, ..., 0) and the radius is 1. Let u be the endpoint of the segment (so that ‖u‖² = 1) and let the angle in radians be θ. The blue sector is all points v such that ‖v‖² ≤ 1 and u·v ≥ ‖u‖ ‖v‖ cos θ = ‖v‖ cos θ. To find the axis-aligned bounding box in d dimensions, we need to find the 2d vectors v that minimize/maximize each individual coordinate, i.e., given a vector e such that either +e or −e belongs to the axial basis (e.g., e = (0, −1, 0, ..., 0)) we want to maximize e·v subject to the restrictions on v.

maximize e·v
subject to
‖v‖² ≤ 1
u·v ≥ ‖v‖ cos θ

We observe first that without loss of generality, ‖v‖ = 0 or ‖v‖ = 1, since the objective is linear and the other points lie on a convex combination of these. Let's focus on the latter case.

maximize e·v
subject to
‖v‖² = 1
u·v ≥ cos θ

Second, there exists an optimal solution that lies in the space spanned by e and u. Given any optimal solution, we can take the orthogonal projection into that space without increasing its norm or changing the dot product with e or u, so the projection is feasible and optimal too.

Therefore we rewrite the problem in terms of coefficients α and β by letting v = αe + βu.

maximize e·(αe + βu)
subject to
‖αe + βu‖² = 1
u·(αe + βu) ≥ cos θ

Let's expand the products and use the fact that ‖e‖² = ‖u‖² = 1.

maximize α + β(e·u)
subject to
α² + 2αβ(e·u) + β² = 1
α(e·u) + β ≥ cos θ

Now we have a case analysis. Ignoring the linear constraint, the objective is at most 1, hence the solution α = 1 and β = 0 (i.e., v = e) is optimal. This solution is feasible only if e·u ≥ cos θ.

If this solution is not feasible, the linear constraint must be tight: α(e·u) + β = cos θ, or β = cos θ − α(e·u). Then we can substitute, solve the resulting quadratic equation, and take the solution that scores better (unless they both score negative, in which case the bound is 0).