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.
Best Answer
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.