Fascinating question, but I don't have any hard answers.

I assume you're looking at the simpler line_intersect function on page 439 (1st ed). Have you run Devel::DProf on a semi-reasonable sample to see where the time is being burnt?

Glancing at the code, I would assume that bounding_box and determinant would be good candidats for memoization, which will get you the on the RAM side of the space/time trade-off. You do have a lot of RAM, right?

g r i n d e r