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

<ul>
<li>The dimension <span class="math-container">$d$</span> is part of the input, and the question is whether you can separate set <span class="math-container">$B$</span> from set <span class="math-container">$G$</span> by <span class="math-container">$k=2$</span> hyperplanes.</li>
<li>The dimension is <span class="math-container">$d=2$</span> (and the number <span class="math-container">$k$</span> of separating hyperplanes is part of the input).</li>
</ul>

<p>This has been proved in:</p>

<blockquote>
  <p>Nimrod Megiddo<br>
  On the Complexity of Polyhedral Separability<br>
  Discrete and Computational Geometry 3, pp 325-337, (1988).</p>
</blockquote>

CC BY-SA 4.0
2019-12-07T20:55:42.140Z
Thanks for your answer. Polyhedral separability was the keyword I was looking for.
orlp
CC BY-SA 4.0
2019-12-07T21:19:35.790Z
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: https://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
CC BY-SA 4.0
2019-12-07T13:17:19.927Z
2019-12-07T13:17:19.927Z
Gamow
<p>Let <span class="math-container">$\mathbb{R}^d$</span> be our space. We have a single good set of points <span class="math-container">$g$</span>, and a collection of bad sets of points <span class="math-container">$B$</span>. </p>

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

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

CC BY-SA 4.0
2019-12-07T03:19:08.483Z
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
CC BY-SA 4.0
2019-12-07T10:07:32.913Z
@NealYoung Good point! I'll edit the question.
orlp
<linear-programming><computational-geometry><convex-geometry>
Minimal number of hyperplanes needed to separate sets of points from one other set
orlp
# Minimal number of hyperplanes needed to separate sets of points from one other set

(Asked by: username_0 on 2019-12-07)

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)?

**Tags:** linear-programming, computational-geometry, convex-geometry
> **Comments:**
> **username_1**: 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.  
> **username_0**: @NealYoung Good point! I'll edit the question.  

---

## 1 answers

### Answer by username_2 on 2019-12-07. Score: 6 | Accepted answer

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).

> **Comments:**
> **username_0**: Thanks for your answer. Polyhedral separability was the keyword I was looking for.  
> **username_0**: 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: https://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$.  

---

