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$
3
  • $\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$
    – John L.
    Dec 30, 2018 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$
    – John L.
    Dec 30, 2018 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, 2018 at 14:17

1 Answer 1

0
$\begingroup$

There is some printing mistake it seems, the expression S←S−{Ej} must be inside else block otherwise S will always be empty.Since we are adding the elements in if block and removing it at last making no sense. The correct pseudo code looks like below:

$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\qquad S\leftarrow S-\{E_{j}\}\\ \qquad\right\}\\ \qquad i \leftarrow i+1\\ \\ \right \} $

$\endgroup$

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.