Usu's blog

How to count the intersections of n segments in n log n
By Usu, history, 6 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

you can do this with a sweepline approach Bentley–Ottmann algorithm

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +15 Vote: I do not like it

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

      → Reply