4
$\begingroup$

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 ?

$\endgroup$
2
  • 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$ Jul 18, 2015 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, 2015 at 9:17

1 Answer 1

3
$\begingroup$

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

$\endgroup$
9
  • $\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, 2015 at 21:32
  • $\begingroup$ The way they write it makes one think that these are the vertices. $\endgroup$
    – Igor Rivin
    Jul 17, 2015 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, 2015 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, 2015 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, 2015 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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