large since it only uses locally (for each $C_j$) the fact that $\mathcal{X}$ consists of linear classifications; in particular, it does not use the dimension of the ambient space $\mathbb{R}^m$. Now we sketch the argument for an improved bound, and details are provided in the appendix.

First notice that the partial classification $x(p)|_{C_j}$ is completely defined by the value $pc^j$. Thus, if $J \subseteq [K]$ is such that the directions $\{c^j\}_{j \in J}$ form a basis of $\mathbb{R}^m$ then knowing $pc^j$ for all $j \in J$ completely determines the whole classification $x(p)$. Similarly, if we know that $x(p)|_{C_j} \in \mathcal{B}_i^{{v}_j}$ for all $j \in J$, then for each $j \notin J$ we should have fewer possible $\mathcal{B}_i^{{v}_j}$’s where the partial classification $x(p)|_{C_j}$ can belong to; this indicates that some of the sets $\{\mathcal{B}_i^{{v}}\}_{{v}\in L^K}$ do not contain any element from $\mathcal{X}$, which implies a reduced size for the witness sets.

In order to capture this idea, we focus on the space of dual vectors $p$ and define the sets $P^\ell_j = \{p \in {{\ensuremath{\mathbb{R}}}}_+^m : x(p)|_{C_j} \in \mathcal{B}_{i,j}^{\ell}\}$ and $P^v = \{p \in {{\ensuremath{\mathbb{R}}}}_+^m : x(p) \in \mathcal{B}_i^v\}$. Notice that $P^v = \cap_j P^{v_j}_j$ and that $\mathcal{B}^v_i$ is empty iff 