Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My problem is simple, and probably obvious from the title itself, but I'll still clarify it a bit:

I have a rectangle and a polyline (array of N connected points). I need an optimal algorithm that checks if intersection between them exists (true/false).

Could someone please point me to one?

Thanks in advance

share|improve this question
The naïve algorithm (checking for all intersections between lines) seems optimal in terms of asymptotic complexity. You can't really get any better than linear. –  tomasz Aug 6 '12 at 16:01
I imagine if the array is sorted then it might be possible to do something that is logarithmic. A more natural place to ask this question is the CS.SE. –  Jérémie Aug 6 '12 at 17:37
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.