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 ?

  • 1
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Jul 18 '15 at 2:09
  • $\begingroup$ @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) $\endgroup$ – tam Jul 18 '15 at 9:17

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

  • $\begingroup$ 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 $\endgroup$ – tam Jul 17 '15 at 21:32
  • $\begingroup$ The way they write it makes one think that these are the vertices. $\endgroup$ – Igor Rivin Jul 17 '15 at 21:36
  • $\begingroup$ I am asking this since in my case I don't know the set of vertices for $\mathbf{P}_2$. $\endgroup$ – tam Jul 17 '15 at 21:40
  • $\begingroup$ Reading the paper seems to indicate that they don't need $X$ to be the set of vertices. $\endgroup$ – Igor Rivin Jul 17 '15 at 21:49
  • $\begingroup$ 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 ? $\endgroup$ – tam Jul 18 '15 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.