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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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.