0
$\begingroup$

The problem is:

Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ intersections). What is the complexity of this problem as a function of n?

The solution algorithm is given in this paper. $S$ is like an order statistic tree right? I don't understand why the author put $S\leftarrow S - \{E_{j}\}$ outside $else$. Why you would want to remove $\{E_{j}\}$ at the end of every loop?

$i\leftarrow 1 \\ intersections \leftarrow 0\\ S\leftarrow \phi\\ while(i\leqslant2n)\left \{\\ \qquad j \leftarrow \sigma _{i} \\ \qquad if(seen_{j}=FALSE)\left \{/*open\ an\ interval\ for\ j*/\\ \qquad\qquad seen_{j}\leftarrow TRUE\\ \qquad\qquad E_{j}\leftarrow i\\ \qquad\qquad S\leftarrow S\ \cup\ \{i\}\\ \qquad\right \}else\left\{/*close\ the\ interval\ for\ j\ and\ count\ intersections*/\\ \qquad\qquad intersections\leftarrow intersections \ +\ |\{x|x\in S\ \wedge x>E_{j}\}|\\ \qquad\right\}\\ \qquad i \leftarrow i+1\\ \qquad S\leftarrow S-\{E_{j}\}\\ \right \} $

$\endgroup$
  • $\begingroup$ Have you tried running the algorithm by hand step by step for some small examples such as when $n=2$ or $n=3$ or $n=4$? If not, please do it now. If yes, can you tell us what you have found regarding "Why you would want to remove {Ej} at the end of every loop?" $\endgroup$ – Apass.Jack Dec 30 '18 at 11:32
  • $\begingroup$ The phrase "the complexity of this problem" does not make sense to me. If you meant the complexity of the algorithm in that paper, it is $O(n\log n)$ as shown in the paper. $\endgroup$ – Apass.Jack Dec 30 '18 at 11:34
  • $\begingroup$ @Apass.Jack First of all, the problem was quoted from that paper without modification. Not what I meant, it’s what the author proposed in the paper. I think it’s clear enough that the author is talking about the complexity of the algorithm. Second, I don’t care the complexity cause it’s quite obvious. My doubt is about the correctness of the algorithm. In my opinion, I think $S \leftarrow S - E_{j}$ should be in the else block. I want to double check if my understanding is wrong. $\endgroup$ – ch48h2o Dec 30 '18 at 14:17

Your Answer

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

Browse other questions tagged or ask your own question.