Weblog

It's all fun and games till someone does some maths

I've had to a bit more maths at work in the last few weeks, than I usually get to do, and one nice wee problem is this. What is the tightest bounding box you can but around an ellipsoid, when the ellipsoid (like say a rugby ball) may be rotated so that the axes no longer line up with the coordinate axes (like if our rugby ball is sitting tilted on a kicking tee). I couldn't find the answer on web so I though about solving it myself. Now I only needed the answer for a 3D ellipsoid but hey it's a fun question to ask for a general d-dimensional ellipsoid. After struggling away I came up with an algebraic answer for 2 and 3D, a bit later on a came up with a procedure for solving the general problem. After a lot of messy algebra, I came up with a surprisingly simple formulation. A few days later I tried another approach and the result falls out with suprising ease. So click below to see the full solution.

Theorem

Let E be an ellipsoid in R^d centred around the origin so that it has equation
f(x)=x^TAx=1 where A is symmetric, and v be a vector in R^d, Then the point on E that maximises v.x is x*=(v^TA^-1v)^-0.5A^-1v and the maximum value v.x*=(v^TA^-1v)^0.5
Proof
As x* is a maxima, the tangent plane to the surface through x* is perpendicular to the vector v. By definition the tangent plane is perpendicular to the normal through x* so the normal and v are parallel.
The normal is n=Δf(x*)=2Ax* so we can write 2Ax*=2kv for some nonzero k, this rearranges to give v=kA^-1x* and after substituting into the the equation of E and simplifying we get 1=k²v^TA^-1v so k=(v^TA^-1v)^-0.5, and the results for the values of x* and v.x*=v^Tx* follow.

Corollary:

The minimum axis-orientated bounding box of E above is [-m, m] where m_i=(A^-1)_ii.
Proof: The maximum bounds follow from applying the above theorem to each of the standard basis vectors eⁱ in turn, noting that e^j.y=y_i and (e^j)^TMe^k=M_jk for any vector y and any matrix M, the minimal bound then follows by the symmetry of E.

The theorem with its general v can also be used for other things... I've though of at least one other application in our software, and it's trivial to prove that the result relatiing the eigenvalues and eigenvectors of the matrix to the directions and lengths of the axes of the ellipsoid.

Two for one

Okay... due to supreme lazyness, I haven't posted anything for a few weeks, and guess what that means, yep you guessed it - another post dominated by uncommented on links. But this post is special, yes for this limited time offer you get not one, but two links for the ultra low price of absolutely nothing... so yeah, check out our stock below, and don't forget to take advantage of this amazing deal. Get 'em while they're hot.. or at least not completely stale..

• TAP out: America as a one party state versus A wake-up call for American media.
• Kant and the Iraq war versus A tale of two fences.
• BeliefNet on Mel's Passion versus Bayes on God.
• The geek shall inherit the Earth versus The Perpetual Adolescent.
• And finally, What's popcorn in Aramaic? versus You have two cows....
  

Okay... wasn't that fun.