sieunhanbom04's blog

A geometry problem
By sieunhanbom04, history, 7 years ago, In English

Given 2 sets of point namely P={p1,p2,...,pn} and Q={q1,q2,...,qn}. Those 2n points all lie on the unit circle. Draw segment (pi,qi). Determine the number of intersecting pair of segments. The required complexity for this problem are O(nlogn^2) and O(nlogn). Could someone give me a hand in this problem?

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

»
7 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

I'm supposing all the points are distinct. After ordering all the points, it is possible to map each point to an integer in the range [1, 2N] based on its position. After that, each line segment can be seen as a segment [Li, Ri]. Now, for each segment [Li, Ri], you need to count how many segments [Xj, Yj] are there such that Xj < Li < Yj < Ri; i.e., the segments intersect. This can be done with line sweep + fenwick tree (for each starting point Li in the line sweep you count how many "active" ending points Yj are smaller than Ri). Some care must be taken with the cyclic segments but I think this should be easy.

By the way, can you provide the problem link, please?

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

    Not exactly this problem, but similar problem here. I think in this problem we have to find count of intersecting pairs, then answer is ((cnt_intersecting_pairs) + n + 1). If I'm wrong, please correct me.

    Some solvers of this problem told it is solved by fenwick tree as you mentioned.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is just an problem in my "algorithm design and analysis" course so I do not have link for this problem. By the way, we share the same thought on this problem, however, the cyclic segments appear really hard to handle, not that easy.

    → Reply