Covering the edges of a complete geometric graph with convex polygons

Given a set $P$ of $m \geq 3$ points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in $P$ such that the edges of all these polygons contain all the ${m \choose 2}$ straight line segments determined by the points of $P$. 

We show that if $m$ is odd, the answer is $\frac{m^2-1}{8}$ regardless of the choice of $P$. The answer in the case where $m$ is even depends on the choice of $P$ and not only on $m$. Nearly tight lower and upper bounds follow in the case where $m$ is even.   

Based on joint work with Rom Pinchasi.