score:2

The problem isn't eliminating for loops, at least in the way that you're thinking of it. Rewriting this in LINQ is just going to hide the for loops but they'll still be there. And that's the fundamental problem. Your algorithm, as written, is O(n^2) and that's why you see a ridiculous explosion in time as you go from 20,000 elements to 300,000 elements. You're doing 400,000,000 comparisons in the first case, and 90,000,000,000 in the second case and it will continue to grow like O(n^2).

So, the question you really want to ask is: is there an algorithm with time complexity better than O(n^2) for this problem?

Frankly, I don't know the answer to that question. I suspect that the answer is no: you can't know if a point is contained in some rectangle without comparing it to all the rectangles, and you have to inspect all the points. But maybe there's a clever way to do it such as computing the convex hull of all the rectangles and use that somehow?

This problem is an example of the field of computational geometry.


Related Articles