# 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,

• 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 E 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