4
$\begingroup$

Suppose I have a collection of good convex sets and bad convex sets in $\mathbb{R}^d$ (where $d$ can be big). Each convex set is defined by a series of closed ranges in each dimension $d$ - a hyperrectangle if you will. For 2D an example set could be $\{(x, y) : x \in [1, 5]\wedge y \in [-2, 3]\}$. All sets are sparse, that is, for the majority of the dimensions the convex set in that dimension just covers range $[0, 0]$, each set only has a non-zero width in a couple dimensions. This means each hyperrectangle could be efficiently described by listing its vertices despite the high dimensionality.

If the convex hull of the good sets is disjoint from all bad convex sets, there exists a set of hyperplanes (AKA inequalities) that together separate the good from the bad sets. The convex hull immediately gives you such a set of hyperplanes, but it's not minimal - it uses more hyperplanes than necessary.

Can we efficiently compute a minimal set of hyperplanes that separates the good from the bad sets? If one hyperplane suffices we can find it using linear programming, but I don't know how to compute it if more than one hyperplane is needed.

If the answer is no, can we get at least an efficient heuristic/greedy algorithm?

$\endgroup$
  • $\begingroup$ A weak heuristic would be to start with the convex hull, and throw out any hyperplanes that have no bad points on the other side. But in general the optimal solution need not be a subset of convex hull hyperplanes -- e.g. in 2D, with the 4 vertices of a square and a point slightly to the right of the centre, with the two rightmost points being bad, no single edge of the (triangular) convex hull separates good from bad, though a single vertical line works. $\endgroup$ – j_random_hacker Dec 3 '19 at 0:31
  • $\begingroup$ A better heuristic would be to solve a Minimum Set Cover problem in which the universe consists of the bad points, and for each hyperplane in the convex hull we have a set consisting of those bad points which it cuts off. This is NP-hard and also doesn't get around the problem that you might need hyperplanes not in the convex hull for optimality, but it does let you add arbitrary other good-point-preserving hyperplanes as sets to try to get a better solution -- the only issue is how to come up with them. $\endgroup$ – j_random_hacker Dec 3 '19 at 0:37
  • $\begingroup$ @j_random_hacker With a linear program you can find a single hyperplane that separates all the good sets from at least 1 bad set. If we let $w$ be the weights (one for each dimension), $g$ the vertices of the good hyperrectangles (as a vector of coordinates) and similarly $b$ for the bad ones, we can solve $\bigwedge_i (w^T g_i \leq C - \delta) \wedge \bigwedge_i (w^T b_i \geq C + \delta)$. With that in mind we can keep try adding each bad set to the program and see if it stays satisfiable. Then all the bad sets we couldn't add get handled in the next hyperplane to make a greedy algorithm. $\endgroup$ – orlp Dec 3 '19 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.