#### Approximating a subproblem.

To solve [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on [<span style="font-variant:small-caps;">B$_1$-VPG</span> ]{}graphs, Lahiri et al. [@LahiriMS15] first considered a subproblem in which all paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}are assumed to be of [$\llcorner$]{}-type. So, suppose for now that $G$ is a [<span style="font-variant:small-caps;">B$_1$-EPG</span> ]{}graph such that all paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}are of [$\llcorner$]{}-type. The algorithm sorts the paths in [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}by the $x({\texttt{corner}}(P))$ of all paths $P$ and considers the vertical line $\ell: x=x_{med}$, where $x_{med}$ is the middle point between $x({\texttt{corner}}(P_{\lfloor n/2\rfloor}))$ and $x({\texttt{corner}}(P_{\lfloor n/2\rfloor+1}))$ in the ordering. Then, the paths are partitioned into three groups: the set $I_L$ of paths that lie to the left of $\ell$, the set $I_R$ of paths that lie to the right of $\ell$ and the set $I_M$ of paths that intersect $\ell$. The algorithm solves [<span style="font-variant:small-caps;">Maximum Independent Set</span> ]{}on $I_L$ and $I_R$ recursively and returns the larger of $S(I_L)\cup S(I_R)$ and $S(I_M)$ as the solution, where $S(A)$ is a maximum independent set on the set of paths in $A$.

To compute $S(I_M)$, the algorithm performs the above divide-and-conquer approach on the sorted $y({\texttt{corner}}(P))$ of only paths $P\in I_M$; hence, partitioning the paths in $I_M$ into three analogous groups $I'_L$, $I'_R$ 