Lower bounds for the number of hyperplanes separating two finite sets of points

We consider the $NP$-hard polyhedral separability problem for two subsets $A$ and $B$ of points in general position in $\mathbb R^d$ with the fewest number of hyperplanes in the sense of boolean functions from a given class $\Sigma$. Both deterministic and probabilistic lower bounds are obtained for this number for two different classes of functions $\Sigma$.