### usureluflorianr's blog

By usureluflorianr, history, 7 days ago, ,

Hey! Does anybody know how to solve this? Given n segments, count how many pairs of segments have a common point. There are no 2 overlapping segments and the segments are can make any angle with the origin of the cartesian plane.

•
• +6
•

 » 7 days ago, # |   +5 you can do this with a sweepline approach Bentley–Ottmann algorithm
•  » » 7 days ago, # ^ |   +5 But if number of crossings is big (quadratic, let's say) this algorithms is bad since it explicitly lists all of them and count them one by one. However, I am not sure if the original problem is solvable at all in something like O(n^1.999) or whatever.
•  » » » 7 days ago, # ^ | ← Rev. 3 →   +15 well there are improved versions for example in $O(n^{\log_2(1+\sqrt{5})}) \approx O(n^{1.695})$ from Chazelle or in $O(n^{1.5} \log{n})$ from Mairson and Stolfi. Thats still slower than $O(n \log{n})$ but i don't know any better algorithms for this or any lower bounds for the counting problem...