Algorithm to find a facet of a polyhedron given the vertices? I have a set of points $X=\{x_1,\ldots,x_N\}$ on the unit sphere in $\mathbb{R}^d$ ($N>d\ge 3$). What is an algorithm to find any facet of the polyhedron whose vertices are $X$?
The set $X$ has some features that may be helpful:

*

*It is highly symmetric in the sense that for each pair $x,x'\in X$ there is an isometry that maps $X$ to itself while mapping $x\to x'$.  ($X$ "looks the same" from the vantage of any point in the set.) For this reason it is sufficient for me to find any facet; by symmetry the others will look the same.

*I can efficiently enumerate the points closest to any given $x\in X$.

Note, I am not looking for a software tool. The set $X$ is a theoretical construct and I wish to use my knowledge about $X$ and some facet-finding procedure TBD to determine the facet geometry analytically.  An example of the kind of answer I am looking for might be something like "1. Pick any vertex.  2. Find one of its nearest neighbors.  3.  Find one of that vertex's nearest neighbors ... "
 A: Inspired by Matt F's response, I figured out a solution (I think). Intuitively, a procedure that will find some facet starting from a given vertex $x_1$ is the following:  Start with a hyperplane containing the point $x_1$ and orthogonal to the vector $x_1$. Then tilt the hyperplane in some direction until it intersects another vertex.  Using those two vertices as pivot points, tilt the hyperplane in some other direction until it intersects a third vertex, and so on until you have $d$ linearly independent vertices.
More formally, let $x_i$ denote the vertex selected in iteration $i$ and let $u_i$ denote a vector in the span of $x_1,...,x_i$ and orthogonal to the face defined by these vertices. "Tilting the hyperplane" is achieved by adding to $u_i$ any vector orthogonal to $x_1,\ldots,x_i$.
Given an initial vertex $x_1$, start by taking $u_1 = x_1$.  Then to find $x_{i+1}$ and $u_{i+1}$,

*

*Define
$$
\lambda_i(x) = \frac{1 - x \cdot u_i}{||\Pi_i x||}
$$
where $\Pi_i$ is the projector onto the subspace orthogonal to $x_1,\ldots,x_i$.

*Take
$$
x_{i+1} = \arg \min_{x\in X} \lambda_i(x) \\
u_{i+1} = u_i + \lambda_i(x_i) \frac{\Pi_i x_i}{||\Pi_i x_i||}
$$
After $d$ iterations, one obtains $d$ linearly independent vertices $F = \{x_1,\ldots,x_d\}$.  It can be shown inductively that $u_d \cdot x_1 = \cdots = u_d \cdot x_d = 1$ and $u_d \cdot x < 1$ for all $x\in X - F$.  Thus $F$ defines a facet.
