# Thousands of rays intersections with Triangles in 3D space [closed]

Hi

There are thousands of rays and triangles. We need get all the intersection points. If we use the normal two level loops,we need O(m*n) time complexity.Is there any way to low the time complexity fronm O(m*n) to O(m* logn) or O(logm*n)?

Best Regards,

-

## closed as off topic by Greg Kuperberg, Reid Barton, Anton GeraschenkoDec 23 '09 at 19:08

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

StackOverflow would be a right place for computer science questions. – Ilya Nikokoshev Dec 23 '09 at 10:39
I don't know -- algorithmic geometry seems to have one foot in mathematics. I have a different issue with the question: I feel that it is very vaguely worded. – Pete L. Clark Dec 23 '09 at 11:38
I think the subject matter is OK and, piecing together all the clues, I think I know what the question must be. That said, I shouldn't have to piece together clues. ET, can you confirm that the following is correct: we have m triangles and n rays in three dimensional space. I am not sure whether or not the rays all pass through the origin. We wish to find every pair (ray, triangle), so that the ray and triangle meet. There is an obvious O(mn) algorithm -- check each pair. Can we do better? – David Speyer Dec 23 '09 at 14:38
My vote is to ask at StackOverflow. – Greg Kuperberg Dec 23 '09 at 16:45
In general, you cannot do better, because there may be mn intersections. – Reid Barton Dec 23 '09 at 17:32