Dear all,

I am currently stuck at a problem which seems too easy to be stuck at to me...

### Summary

Let $H$ be the convex hull of the points $d_1,\ldots, d_n\in \mathbb{R}^d$. How can one compute \[\min_{x\in H}||x||^2_2 \] efficiently?

### Conditions one should know about

When I talk about efficiency in this question, I do not talk about a polynomal time algorithm. For my purpose, $n$ is really small, $n=4$ should do in almost all cases. (Even a fast solution for the special case $n=4$ would be highly appreciated). Also, $d=2$ is the main dimension of interest, whereas it might be possible that at some time this might also be a question for the three dimensional space. This question is embedded in an algorithm that will be called thousands of times within a very short timeframe. In short, I am looking for an *efficient* way in terms of "Do I need 20 or 40 FLOPS"...

### First thoughts

Of course, one could take this problem as a Quadratic Program by writing $D=[d_1,\ldots, d_n]$ and then minimizing $x^tD^tDx$ with respect to $\sum_{i=1}^d x= 1$ and $x_i\geq 0$. However, I just feel this might be overkill for such a simple problem.

I also thought about taking a least norm approach, but here I do not really get a grip on formulating the problem the right way to throw some (to me) known technique at it.

Also, one could compute the convex hull explicitly and then try to locate 0 geometrically around the hull and only compute the corresponding distance to the hull. As I made a rough sketch to the algorithm I had in mind, I realized this also gives me quite a lot of things to compute and cases to distinguish between.

Your ideas would be greatly appreciated.