2
$\begingroup$

Given to me is a set of points $p_1,...,p_n\in\Bbb R^d$ in general position. I want to determine only the edges of the convex hull $C:=\mathrm{conv}\{p_1,...,p_n\}$, and this as efficient as possible. Especially, I do not want to compute the complete convex hull with all its faces and then extract only the $1$-faces from the result. This would be too much overhead.

In an abstract form, the problem states as follows:

For what pairs $(p_i,p_j)$ there exists a linear function $\Bbb R^d\to\Bbb R$ that takes its maximum exactly on $p_i$ and $p_j$?

We can assume that the origin is inside the convex hull, and that all points will be vertices of the convex hull.

A general algorithms would be welcome. However, for my specific use-case we can further assume that all the points are of the same kind, i.e. for any two of the points, say $p_i$ and $p_j$, there is a symmetry transformation $\phi$ of the arrangement, so that $\phi(p_i)=p_j$.


Appraoch

My previous approach was as follows. Given a pair $(p_i,p_j)$:

  • Compute $q:=p_i+p_j$.
  • Find the points that maximize $\langle p_i,q\rangle$.
  • If these are exactly the points $p_i$ and $p_j$ (not more, not less), then they form an edge. Otherwise, they do not.

The algorithm does not give false positives, however it gives false negatives. So it might find too few edges. I think it is about choosing $q$ in a better way. But I have no idea how to do this in general.


This question is different from my other question on convex hulls, as here I ask for efficient algorithms instead of abstract techniques, and also I have other assumptions on the point set.

Further, I already have a specific algorithm in mind, where I would prefer to only hear about a better working choice for $q$. Of course, other approaches are welcome too.

$\endgroup$
1
$\begingroup$

For each pair $\{\mathbf p_i, \mathbf p_j\}$, we can find $\mathbf q$ by solving a linear program. For example, the linear program $$ \min_{\boldsymbol \lambda} \left\{0 : \sum_{k \ne i,j} \lambda_k \mathbf p_k = \lambda_i \mathbf p_i + \lambda_j \mathbf p_j, \sum_{k \ne i,j} \lambda_k = 1, \lambda_i + \lambda_j = 1, \boldsymbol \lambda \ge \mathbf 0\right\} $$ is infeasible when $\mathbf p_i$ and $\mathbf p_j$ form an edge (it represents "find a point in the convex hull of $\mathbf p_i$ and $\mathbf p_j$ which is also in the convex hull of the other points"). Therefore its dual, which is (after some cleaning up) $$ \max_{x,y,\mathbf q} \{ x-y : \langle \mathbf p_i, \mathbf q\rangle \ge x, \langle \mathbf p_j, \mathbf q\rangle \ge x, \langle \mathbf p_k, \mathbf q\rangle \le y \text{ for } k \ne i,j\}, $$ is unbounded when $\mathbf p_i$ and $\mathbf p_j$ form an edge. Solve this dual until we have $x-y>0$, and then $\mathbf q$ should be a direction maximized only on $\mathbf p_i$ and $\mathbf p_j$.

This answer does not assume any symmetry, but does require all points $\mathbf p_1, \dots, \mathbf p_n$ to be extreme points, as pointed out in the comments.

$\endgroup$
  • $\begingroup$ Thank you for your answer, it was incredibly helpful! I just need to add one note to the answer, which should not be overlooked: if only one of the points $\mathbf p_i$ and $\mathbf p_j$ lies on the boundary of the convex hull, then the primal program might give false positives. This happens, when the non-boundary point (say $\mathbf p_i$) does not lie in the convex hull of the other points (all points besides $\mathbf p_i$ and $\mathbf p_j$). While this is not a problem in my case (all point lie on the boundary was an assumption), I think it is worth to mention it as a hidden assumption. $\endgroup$ – M. Winter Sep 12 '18 at 14:01
  • $\begingroup$ Oh, I see. So $\mathbf p_j$ is a convex combination of the other points when we do include $\mathbf p_i$, but not when we don't. $\endgroup$ – Misha Lavrov Sep 12 '18 at 14:27
  • $\begingroup$ "[...] when the non-boundary point does not lie in the convex hull of the other points.", e.g. take the vertices and the center of a tetrahedron. Every pair would "give an edge". $\endgroup$ – M. Winter Sep 12 '18 at 14:27
  • $\begingroup$ Exactly, sorry for deleting my comment. I wasn't sure about understanding yours correctly. And thank your for including my point into your answer. $\endgroup$ – M. Winter Sep 12 '18 at 14:27

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.