Can anybody help me prove the NP-hardness of the following question: Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in conv(\{x_i|i\in S\})$ and $x_0 \in conv(\{x_i|i\in[m]\backslash S\})$?
6
-
$\begingroup$ I'm having trouble with your notation. 1) If this is a computational decision problem, what do you mean by input size if the vectors are real-valued? 2) What do you mean by $[m]$? If [m] means $\{1,\ldots,m\}$ I suggest using another notation for $x_0$ seeing as it has a completely different role in the story. 3) I'm guessing that conv mean convex hull? $\endgroup$– David FeldmanCommented Mar 18 at 5:40
-
$\begingroup$ For fixed n it is polynomial in m. en.m.wikipedia.org/wiki/… $\endgroup$– Lajos SoukupCommented Mar 18 at 6:01
-
2$\begingroup$ I should be clearer. $x_0, x_1, ..., x_m \in \mathbb{Q}^n$, and $[m] = \{1,...,m\}$. $conv(\cdot)$ means the convex hull of the input. Both $n, m$ are not fixed. $\endgroup$– Robeto LeoCommented Mar 18 at 12:30
-
$\begingroup$ Thought: Is the problem any easier if $x_1,\ldots,x_m\in \{0.1\}^n$? That has a more combinatorial flavor. Maybe that's already NP-hard, and maybe still if you assume $x_0=(1/2,1/2,\ldots)$. $\endgroup$– David FeldmanCommented Mar 19 at 19:11
-
$\begingroup$ Thought: Your question implicitly defines a polyhedral complex, call it, say, the disjoint-reasons hull, so all the points in the convex hull for disjoint reasons. It's the union of a lot of intersections of simplexes. A related but purely geometrical question would ask how complicated this complex get (number of vertices, edges, etc.) $\endgroup$– David FeldmanCommented Mar 19 at 19:20
|
Show 1 more comment