the $\underline{w}_i^{{v}}$ and $\overline{w}_i^{{v}}$’s of appropriate size corresponding to meaningful $\mathcal{B}_i^{{v}}$’s: set $\mathcal{W}_i^+ = \{\underline{w}_i^{{v}} : {v}\in L^K, \mathcal{B}_i^{{v}} \cap \mathcal{X} \neq \emptyset, a_i(\underline{w}_i^{{v}}) \ge (1 - \epsilon/2) B\}$ and $\mathcal{W}_i^- = \{\overline{w}_i^{{v}} : {v}\in L^K, \mathcal{B}_i^{{v}} \cap \mathcal{X} \neq \emptyset, a_i(\overline{w}_i^{{v}}) \le (1 - 3\epsilon/2) B\}$.

It is not too difficult to see that, say, $\mathcal{W}_i^+$ is a witness set for $\mathcal{X}_i^+$: If $x \in \mathcal{X}_i^+$ belongs to some $\mathcal{B}_i^{{v}}$, then $\underline{w}_i^{{v}}$ belongs to $\mathcal{W}_i^+$ and is easily shown to be a witness for $x$. However, if $x$ does not belong to any $\mathcal{B}_i^{{v}}$, by having too large $a_i(x)$, the idea is to find $x' \subseteq x$ which belongs to some $\mathcal{B}_i^{{v}}$ *and* to $\mathcal{X}$, and then use $\underline{w}_i^{{v}}$ as a witness for $x$. We note that considering $B_i^{{v}}$’s for side lengths at most $B + m$ and only adding witnesses for $B_i^{{v}}$’s which intersect $\mathcal{X}$ are crucially used for bounding the size of $\mathcal{W}_i^+$ and $\mathcal{W}_i^-$.

\[lemma:wWitness\] The sets $\mathcal{W}_i^+$ and $\mathcal{W}_i^-$ are witness sets for $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$.

[*Bounding the size of witness sets.*]{} Clearly the witness sets $\mathcal{W}_i^+$ and $\mathcal{W}_i^-$ have size at most $|L|^K$. Although this size is independent of $n$, it is still unnecessarily 