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, ...)



Is this problem of selecting points NP-hard?
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.


