# Counting chords intersections in a circle

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 \}$$

• 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?" – John L. Dec 30 '18 at 11:32
• 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. – John L. Dec 30 '18 at 11:34
• @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. – ch48h2o Dec 30 '18 at 14:17