# Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project.

Say I have two sets of points in three dimensional Cartesian space: A and B.

The problem I would like to solve is to find the convex hull V of a subset of A that maximizes $|\{x|x \in A \wedge x \in V\}| - |\{x|x \in B \wedge x \in V\}|$, preferably in polynomial time.

If the convex hulls of A and B are disjoint then there is no problem. The case I would like help with is when some points from set B may fall inside the convex hull of A.

• Optimal convex hull of what? Do you want to select some subset of $A\cup B$ and take its convex hull? Or do you mean just any convex set? – joriki Jun 22 '16 at 9:52
• I guess I am after the convex hull V of a subset of A that maximizes |{x|x∈A∧x∈V}|−|{x|x∈B∧x∈V}|. – atomice Jun 22 '16 at 11:00
• You should add that to the question -- the question should stand for itself without the comments. – joriki Jun 22 '16 at 11:00