9
$\begingroup$

This is from Jeffrey Erickson's Algorithms notes

Problems 15

Problem 14 asks for an algorithm to count "inversions," in an array(the number of pairs of items out of sorted order) in $\Theta(n\log(n))$ time. I will assume that this is solved in the question that follows.

Problem 15(a). asks to count intersections of lines from $y=1$ to $y=0$. My thought was to sort the $p_i$ by distance from the origin then assign new indices by index in the sorted array(taking $\Theta(n\log(n)$) time using merge sort). Then put the $q_i$ in an array sorted by index. The number of inversions in this array can be counted in $\Theta(n\log(n))$ using (14). and it will be the number of intersections.

Is this right?

15(b) and 15(c) ask to count the number of intersections of secant lines on a circle in $n\log^2(n)$ time and $n\log(n)$ time respectively. Here is where I am completely stuck. I don't see how to apply a solution to (a). to (b). Do you stretch the circle out somehow? Or divide the points in two?

enter image description here

Any help is appreciated.

$\endgroup$
5
  • $\begingroup$ What do you mean by "intersections of lines from $y=1$ to $y=0$" ? Do you mean that each line (assumed non-horizontal !) is described by the abscissas of the intersection points $(x_i,1)$ and $(x'_i,0)$ with these two lines $y=1$ and $y=0$? $\endgroup$ – Jean Marie Jul 9 '17 at 19:32
  • 1
    $\begingroup$ @Jean Marie I don't think that is what I mean. The link has a great picture that makes it clear what the question is about. I'll try to add it to my question. $\endgroup$ – Retired account Jul 9 '17 at 20:06
  • $\begingroup$ Looking forward to the answer for this one! It's easy to make an algorithm that solves the unit circle case, but difficult (for me) to find one that makes use of the solution to (a). $\endgroup$ – Jens Jul 13 '17 at 17:27
  • 1
    $\begingroup$ @Sorry for being slow, but could you describe how to solve part(c).? Or just give a hint. $\endgroup$ – Retired account Jul 13 '17 at 17:35
  • 1
    $\begingroup$ I'm not @Sorry. :-) Anyway, I didn't say I had a solution for (c), just that I had an algorithm for solving the circle case. I think my algorithm is $O(n^2)$. $\endgroup$ – Jens Jul 14 '17 at 14:00
4
+100
$\begingroup$

Parameterize the unit circle, say from $0$ to $2\pi$, and let your points $p_1,\ldots,p_n$ and $q_1,\ldots,q_n$ be given by their parameter value.

W.l.o.g. we may assume that $p_1<\ldots<p_n$ (this may be ensured by a preliminary sorting step which takes $O(n \log n)$). Furthermore assume that $p_i<q_i$ because changing the orientation of a line segment does not change the number of intersections.

Impose a lexicographic order $\prec$ on the points: $p_1 \prec q_1 \prec p_2 \prec q_2 \prec \ldots \prec p_n \prec q_n$. When the points $p_1,\ldots,p_n,q_1,\ldots,q_n$ are ordered w.r.t. $<$ (i.e. parameter value), let $\nu_\prec$ be the number of inversions w.r.t. $\prec$. Moreover, let $\nu_q$ be the number of inversions in the list $q_1,\ldots,q_n$ (i.e. ordered by index) w.r.t. $<$. All of these can be calculcated in $O(n \log n)$ according to your preliminaries.

Let $1\leq i<j \leq n$. Then we distinguish three different cases (no others are possible due to our assumptions):

  1. $p_i<q_i<p_j<q_j$: There is no intersection. There are no inversions.
  2. $p_i<p_j<q_i<q_j$: The line segment from $p_i$ to $q_i$ intersects the line segment from $p_i$ to $q_i$. There is one inversion w.r.t. $\prec$ ($p_j \nprec q_i$).
  3. $p_i<p_j<q_j<q_i$: There is no intersection. There are two inversions w.r.t. $\prec$ ($p_j \nprec q_i$ and $q_j \nprec q_i$), and one inversion $q_j<q_i$ in the ordered list $q_1,\ldots,q_n$.

Therefore I conjecture that the number of intersections is $\nu_\prec-2\nu_q$.

Note though that the actual task was to find a devide-and-conquer algorithm, not to reduce the problem to something we can already solve (even if that happens using devide-and-conquer).

$\endgroup$
2
  • $\begingroup$ But this is$ n\log(n)$ correct? I guess this solves (c), but it leaves (a) a mystery. $\endgroup$ – Aperson123 Jul 18 '17 at 15:03
  • $\begingroup$ @Aperson123: Case (a) is easier. Once $p_1<\ldots<p_n$ are in increasing order (you may no longer assume $p_i<q_i$), the number of intersections is simply the number of inversions in the list $q_1,\ldots,q_n$ (denoted $\nu_q$ above). (b) remains a mystery. $\endgroup$ – Stefan Böttner Jul 19 '17 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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