AS ALGO 3

Problem 2

Exercise 336.1(Exercise).

Describe and algorithm to find the size of the largest subset of segments in $S$ such that every pair crosses.

Let $P$ be the set of points and $S$ be the set of edges. Represent edges by objects with properties $\text{left}$, $\text{right}$, and $\text{id}$, where $e.\text{left},e.\text{right}\in P$, $e.\text{left}<e.\text{right}$, and $e.\text{id}\in [\mathrm{1..}m]$ for all edges $e\in S$.

Let $E[\mathrm{1..}n-1]$ be a 2d array such that $E[i]$ is an array containing all edges $e$ such that $e.\text{left}=i$ sorted in decreasing order of the property $\text{right}$. Assign $e.\text{id}$ to be the index of $e$ in $\text{flatten}(E)$ for all $e\in S$.

Let $N[\mathrm{1..}n-1]$ be an array such that $N[i]$ is the number of edges $e$ satisfying $e.\text{left}⩽i$.

Let $F[\mathrm{2..}n]$ be a 2d array such that $F[i]$ is an array containing all edges $e$ such that $e.\text{right}=i$ sorted in decreasing order of the property $\text{left}$.

$$\begin{array}{rl}& \text{MaximumClique}(N,F):\\ & ans\leftarrow 0\\ & \text{for }i\text{ in }[\mathrm{1..}n-1]:\\ & ans=\text{max}(ans,\text{LIS}(\text{map}(e\to e.\text{id},\text{filter}(e\to e.\text{id}⩽N[i],\text{flatten}(F[i+\mathrm{1..}n])))))\\ & \text{return }ans\end{array}$$

Complexity

The preprocessing requires $O(m\log m)$ time. $\text{MaximumClique}(N,F)$ runs in $O(mn\log m)$ time.