2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – joriki Jun 22 '16 at 9:52
  • $\begingroup$ 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}|. $\endgroup$ – atomice Jun 22 '16 at 11:00
  • $\begingroup$ You should add that to the question -- the question should stand for itself without the comments. $\endgroup$ – joriki Jun 22 '16 at 11:00

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.