Is this problem of selecting points NP-hard? I have an optimization problem related, in a certain way, to the expression of a set of points with the least number of points and I don't know if it is NP-hard (or not).
More formally, I have a ground set $U$ of points with coordinates $(x_i,y_i)$ for $i=1,...,n$.
Given an integer $k\leq n$, the decision problem consists in finding a subset $I$ (made of $k$ points) of $U$ such that every point of $U$ can be written as the convex combination of at most two points of $I$.
For example, let $U=\{(0,0) ; (1,3) ;(2,6); (3,0);(2,3/2);(4,3);(6,0)\}$.
There is a solution with $k=4$ wich is $I=\{(0,0) ; (2,6); (4,3);(6,0)\}$.
Indeed, we have $(1,3)=\frac{(0,0)+(2,6)}{2}$; $(2,3/2)=\frac{(0,0)+(4,3)}{2}$ and $(3,0)=\frac{(0,0)+(6,0)}{2}$.
IP formulation
Let $C_{ij}$ be the indices of the points belonging to $U$ which can be expressed as a convex combination of $(x_i,y_i)$ and $(x_j,y_j)$.
I think all these $C_{ij}$'s can be computed in $O(n^2)$ time.
Then we can write the following IP with $O(n^2)$ binary variables:
$$
\min x_1+...+x_n
$$
$$\sum_{(i,j)|p\in C_{ij}}y_{ij}\geq 1 \text{ for all } p=1,...,n,$$
$$y_{ij}\leq x_i, y_{ij}\leq x_j \text{ for all } i,j=1,...,n,$$
$$x_i\in\{0,1\} \text{ and } y_{ij}\in\{0,1\} \text{ for all } i,j=1,...,n.$$
I started looking into Garey & Johnson for some similarities with existing problems, but I don't see how to "express" the condition of the convex combination.
Thanks for any advice! (related problems, ...)
 A: This problem is reducible from VERTEX-COVER. A rough description: let the input graph to VERTEX-COVER be $G = (V, E)$ with $|V| = n$. Choose integer $n << t = O(n^c)$, and create a convex polygon $P$ on $1 + n + 2t$ vertices $C_0$, $C_1$, $\ldots$, $C_n$, $D_1$, $\ldots$, $D_t$, $E_1$, $\ldots$, $E_t$. Choose vertices $V_1$, $\ldots$, $V_n$ on sides $C_0 C_1$, $\ldots$, $C_{n - 1} C_n$. Now, for each edge $ij \in E$ with $i, j \in V$ and $i < j$ add all points on intersections of $V_i D_k$ and $V_j E_l$ with $1 \leq k, l \leq t$. We choose coordinates in such a way that no point of the plane has more than two diagonals of $P$ passing through it, and no three intersection points share non-trivial common lines together with vertices $P$ (other than diagonals of $P$ when intended). 
Obviously, we have to include all vertices of $P$ into $I$. Vertices $V_i$ are already covered by sides of $P$, so we have freedom of including any subset of them. For an edge $ij \in E$ we have to cover all intersections of $V_i D_k$ and $V_j E_l$ either by including one of $\{V_i, V_j\}$ into $I$, or take some of the intersections into $I$; in the latter case, $\Omega(t)$ intersections need to be included, which effectively prohibits us from doing this. We can now see that the minimal size of $I$ is exactly $1 + n + 2t + VC(G)$, where $VC(G)$ is the size of minimal vertex cover of $G$.
The last remark is that we have to make sure that it is possible to choose all coordinates so that length of coordinates of each point is polynomial in $n$, which is technical.
