Cheap rsqrt is usually 12bits precise. Certainly far enough for collision detection. It costs nearly nothing with 3DNow or SSE.

Else the conclusions are :

The separating axis (perp to the segment joining the two last nearest point) can be cached between frames. So the average cost for (last rejection test)ellipsoid/ellipsoid will be 2 calls to GetFurtherPoint(Axis). That is mainl 4 matrix*vector transfos plus 2 cheap rsqrts.

With the second method, I think the worst case (finding two new nearest points) is comparable to OBBox/OBBox in terms of perfs. A chance to add ellipsoids to the primitive list of future collision detecion libs :)

I'll try to test a code for the second method this week-end.