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}$.
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, ...)
EDIT - IP formulation (but still no hardness result)
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.$$