# Minimal number of hyperplanes needed to separate sets of points from one other set

Let $$\mathbb{R}^d$$ be our space. We have a single good set of points $$g$$, and a collection of bad sets of points $$B$$.

We assume that for all $$b \in B$$ the convex hulls of $$g$$ and $$b$$ are disjoint. This means that there exist a hyperplane separating $$g$$ and $$b$$ (which we can find in poly time with linear programming). We could repeatedly cut our space, eliminating one $$b$$ at a time, and be left with a subspace that only contains $$g$$ from our initial sets - this is what we want.

But we can do (a lot) better - we could separate multiple $$b \in B$$ from $$g$$ simultaneously with a single hyperplane. Is there an efficient algorithm that finds the minimal number of hyperplanes needed (and the partition of $$B$$ into groups you eliminate simultaneously)?

• Does your proposed reduction to clique cover actually work? What if you have, say, in $\mathbb{R}^2$, $g$ containing only the origin and $B$ containing three sets, each with a single point on the unit circle, where the three single points are the vertices of a triangle that has the origin in its interior. Then the resulting graph is a 3-clique (because every two of the three points is separable from the origin by a line), so the graph has a clique cover of size 1, but there is no single line that separates all three points from the origin. – Neal Young Dec 7 '19 at 3:19
• @NealYoung Good point! I'll edit the question. – orlp Dec 7 '19 at 10:07

Your problem is NP-complete, even in the following two highly restricted cases:

• The dimension $$d$$ is part of the input, and the question is whether you can separate set $$B$$ from set $$G$$ by $$k=2$$ hyperplanes.
• The dimension is $$d=2$$ (and the number $$k$$ of separating hyperplanes is part of the input).

This has been proved in:

Nimrod Megiddo
On the Complexity of Polyhedral Separability
Discrete and Computational Geometry 3, pp 325-337, (1988).

• Thanks for your answer. Polyhedral separability was the keyword I was looking for. – orlp Dec 7 '19 at 20:55
• Actually, my problem is harder because I wish to eliminate entire sets of points with a single hyperplane rather than individual points. This is because I'm actually interested in eliminating convex regions. If you were to eliminate single points at a time you could get errors like this: i.imgur.com/syw2ghb.png. Nevertheless your answer still applies because my problem is strictly harder and reduces by setting the cardinality of each set to $1$. – orlp Dec 7 '19 at 21:19