3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Dec 7, 2019 at 3:19
  • $\begingroup$ @NealYoung Good point! I'll edit the question. $\endgroup$
    – orlp
    Dec 7, 2019 at 10:07

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. Polyhedral separability was the keyword I was looking for. $\endgroup$
    – orlp
    Dec 7, 2019 at 20:55
  • $\begingroup$ 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$. $\endgroup$
    – orlp
    Dec 7, 2019 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.