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 ... "



Algorithm to find a facet of a polyhedron given the vertices?
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}$,


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$.
2. 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.


