4
$\begingroup$

Suppose you are given two sets $\{p_1, p_2,\dots , p_n\}$ and $\{q_1, q_2,\dots , q_n\}$ of $n$ points on the unit circle. Each point $p_i$ is connected to $q_i$ by a line segment. How could we count the number of intersections of all $n$ line segments in $O(n\log n)$? You could also see the problem in Jeff Erickson's book, Algorithms.

I have read the posts finding the number of intersections of n line segments with endpoints on two parallel lines and find the number of intersections of $n$ chords in $O(n \log^2 n$) time. So I think by use their idea we can solve the problem above, but I get stuck.

$\endgroup$
1
  • 1
    $\begingroup$ It would be helpful to provide the chapter and exercise number, so that others with the same question are more likely to be able to find this page by search. Thank you! $\endgroup$
    – D.W.
    Apr 30, 2022 at 20:05

1 Answer 1

4
$\begingroup$

Fix an arbitrary point on the circle. For example, $p_0$. Each line segment from $p_i$ to $q_i$ can be represented by a pair of numbers $(a_i, b_i)$, where

  • $a_i$ is the clockwise circular distance from $p_0$ to one end of the line segment and
  • $b_i$ is the clockwise circular distance from $p_0$ to the other end of the line segment

such that $a_i<b_i$.

Draw line $y=0$ and $y=1$ on the coordinate plane.

  • For each number $a_i$, let $A_i=(a_i,0)$, a point on $y=0$.
  • For each number $b_i$, let $B_i=(b_i,1)$, a point on $y=1$.

Convince yourself that the line segment from $p_i$ to $q_i$ intersects with the line segment from $p_j$ to $q_j$ iff the line segment from $A_i$ to $B_i$ does NOT intersects with the line segment from $A_j$ to $B_j$.

The number of all unordered pairs of line segments from $A_i$ to $B_i$ is $\binom n2$.

Now the problem is to count the number of unordered pairs of intersecting line segments from $A_i$ to $B_i$. This is the exercise 14 (a) of chapter 1 in the book Algorithms by Jeffe Erickson or the post on StackOverflow as mentioned in the question. I would assume that you can solve that exercise.

$\endgroup$
5
  • $\begingroup$ Thank you. If i want solve the problem in $O(n\log^2n)$ could you give me some hint? Because I can solve exercise 14 (a), but how we can use that to solve exercise 14 (b)? $\endgroup$
    – ErroR
    Apr 27, 2022 at 1:15
  • $\begingroup$ Here is solution that use to count directly the number of pairs of intersecting intervals $[a_i, b_i]$ using "a range query data structure." $\endgroup$
    – John L.
    Apr 27, 2022 at 1:16
  • $\begingroup$ @ART, how did you solve exercise 14(b) in $O(n\log^2n)$? Please come here for a chat. $\endgroup$
    – John L.
    Apr 27, 2022 at 1:20
  • 1
    $\begingroup$ @JohnL. What about when a1 < b1 < a2 < b2? $\endgroup$
    – Sinπ
    Apr 21, 2023 at 7:40
  • $\begingroup$ @JohnL. What about when a1 < b1 < a2 < b2? In this case line segment p1<->q1 and p2<->q2 doesn't intersect and a1<->b1 and a2<->b2 doesn't intersect too. $\endgroup$ Nov 23, 2023 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.