Lower bounds for the number of hyperplanes separating two finite sets of points
Konstantin S. Kobylkin · Proceedings of the Steklov Institute of Mathematics · 2015
We consider the NP-hard problem of polyhedral separability of two finite sets A and B of points in general position in ℝ d by the minimum number of hyperplanes in the sense of a boolean function from a given class Σ. Both deterministic and probabilistic lower bounds are obtained for this number for two different classes of functions Σ.