Блог пользователя Usu

How to count the intersections of n segments in n log n
Автор Usu, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← 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...

      → Ответить