with the case where the $(\pi_t, a^t)$’s lie in a 2-dimensional subspace of $\mathbb{R}^{m + 1}$, where one can show that $\mathcal{X}$ is a union of 2 chains with respect to inclusion. In the special case where the $a^t$’s lie in a 1-dimensional subspace of $\mathbb{R}^m$, we show that $\mathcal{X}$ is actually a single chain (Lemma \[lemma:chain\]) and therefore we can take $\mathcal{W}_i^+$ as *the* minimal set of $\mathcal{X}_i^+$ and $\mathcal{W}_i^-$ as *the* maximal set of $\mathcal{X}_i^-$.

Due to the above observations, we focus on LP’s whose $a^t$’s lie in few 1-dimensional subspaces. In this case, $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$ are sufficiently well-behaved so that we can find small (independent of $n$) witness sets.

\[lemma:witness2Dim\] Suppose that there are $K \ge m$ 1-dimensional subspaces of $\mathbb{R}^m$ which contain the $a^t$’s. Then there are witness sets for $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$ of size at most $(O(\frac{K}{\epsilon} \log \frac{K}{\epsilon}))^m$.

Assuming the hypothesis of the lemma, partition the index set $[n]$ into $C_1, C_2, \ldots, C_K$ such that for all $j \in [K]$ the columns $\{a^t\}_{t \in C_j}$ belong to the same 1-dimensional subspace. Equivalently, for each $j \in [K]$ there is a vector $c^j$ of $\ell_\infty$-norm 1 such that for all $t \in C_j$ 