hey, i want to do a question in which i am given n line segments and i want to find the number of intersection of them. Can anyone tell me the most efficient way i can do it ? I have got some links on google and also from books but i am not getting it. I am not asking for code or something like that and neither it is my homework. So please help me if you can. thanks

5 Years
Discussion Span
Last Post by rithish

thanks you ! but i have implemented for 2 lines. but i am not getting for n line segments. thanks


Suppose I have 1 line, its doesn't has any intersection so p(1) = 0
Now introducing another line, it cuts p(1) at atmost 1 point so p(2) = 1
Again introduce another line, it will intersect above 2 lines in atmost 2 points, but we already have one intersection point so p(3) = 3

Thus we have a recurrsion

p(x) = p(x - 1) + x - 1

Its a mathematical treatment. Hope it works.

Votes + Comments
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.