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 ?

Improve this question
$\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$
    – Joseph O'Rourke
    Commented 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
    Commented Jul 18, 2015 at 9:17

1 Answer 1

Reset to default
3
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .