# Find the minimum distance between two convex hulls

We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex hull of a set of $M$ points, but we don't know which of these points are the vertices. I am trying to find the minimum distance between $\mathbf{P}_1$, which can also be seen as a convex hull, and $\mathbf{P}_2$.

My approach is to define an optimization problem having an acceptable computational complexity. My question is how can we define such a problem ?

• It may help to look at the CGAL implementation here. CGAL formulates it "as an optimization problem with linear constraints and a convex quadratic objective function." They then use an exact solver for quadratic programs. – Joseph O'Rourke Jul 18 '15 at 2:09
• @JosephO'Rourke It's not clear here (section 5.1) if $P$ (or $Q$) is the set of vertices or not. In my case, for $\mathbf{P}_2$ I don't have the set of vertices alone, but a set of $M$ points which contains the vertices and other points ( which will be inside the convex hull constructed using these vertices) – tam Jul 18 '15 at 9:17

This is discussed at length here. (Kaown and Liu, 2009)

• Maybe this is a dumb question, but when they wrote "Given the set $X=\left\{ x_1,\dots,x_m \right\}$. Let the convex hull be $U=\left\{ \sum_i^m\alpha_ix_i \, .. \right\}$... " do they consider the set $X$ as the set of vertices or a set of points that contains the vertices and other points (that will be inside the convex hull)? Thank you – tam Jul 17 '15 at 21:32
• The way they write it makes one think that these are the vertices. – Igor Rivin Jul 17 '15 at 21:36
• I am asking this since in my case I don't know the set of vertices for $\mathbf{P}_2$. – tam Jul 17 '15 at 21:40
• Reading the paper seems to indicate that they don't need $X$ to be the set of vertices. – Igor Rivin Jul 17 '15 at 21:49
• One more question please. In this paper, they don't provide an expression that capture the computational complexity of their algorithm. If we define the problem as a QP (as done here), do you think that their algorithm outperforms the interior point method (as instance) used to solve the QP ? – tam Jul 18 '15 at 22:08