Find convex hull or simplex on hypersphere that enclose all vectors

Question

Assume that we have x1,x2,...xn vectors in d-dimensional (d>=64) hypersphere, How can we find a convex hull or simplex for all of them that encloses all the vectors? can we describe that shape with limited number of vectors?

Answer 1

For any finite set of vectors $V = \{v_1, \ldots, v_n\}$, the convex hull is given by $$\mathcal H(V)=\left\{\sum_{k=1}^n a_kv_k\;\middle|\; \forall k, a_k > 0; \sum_{k=1}^n a_k = 1\right\}$$

Note that this is the entire hull, not just the boundary hypersurface. Also, a point in the hull may be given by many different coefficient sequences $(a_1, a_2, ..., a_n)$.

---

Added: to show that the set defined above is indeed the convex hull of a finite set.

Convex hulls $C(V)$ and the sets $$\mathcal H(V) := \left\{\sum_{k=0}^n a_kv_k\;\middle|\; n \in \Bbb N; \forall k, a_k > 0\text{ and }v_k \in V; \sum_{k=0}^n a_k = 1\right\}$$ satisfy a similar property:

• For any set of vectors $V$ and any vector $x, C(V \cup \{x\})$ is the union of all line segments connecting $x$ to elements of $C(V)$.
• For any set of vectors $V$ and any vector $x, \mathcal H(V\cup \{x\})$ is the union of all line segments connecting $x$ to elements of $\mathcal H(V)$.

To prove the first, Let $\displaystyle C' = \bigcup_{w \in C(V)} \overline{xw}$. Note that $C(V \cup \{x\})$ is a convex set containing $V$, so as the intersection of all such sets, $C(V) \subseteq C(V \cup \{x\})$. And since $C(V \cup \{x\})$ is convex, it must therefore contain all line segments between $x$ and points of $C(V)$. That is, $C' \subseteq C(V\cup \{x\})$.

Conversely, given any two points $a,b \in C'$, there must be $p,q \in C(V)$ such that $a$ lies on $\overline{xp}$ and $b$ lies on $\overline{xq}$. Now $\triangle xpq$ has its base $\overline{pq}$ in $C(V)$, and every point in its interior lines on a segment from $x$ to a point on $\overline{pq}$, and is therefore in $C'$. In particular, the line segmqent $\overline{ab}$ is interior to the triangle, and so is in $C'$. Since $a, b$ where arbitrary, $C'$ is convex. And so $C(V\cup \{x\}) \subseteq C'$.

Hence $\displaystyle C(V\cup \{x\}) = C' = \bigcup_{w \in C(V)} \overline{xw}$ as required.

To prove the second, let $\displaystyle H = \bigcup_{w \in \mathcal H(V)} \overline{xw}$. Note that the elements of $\mathcal H(V\cup\{x\})$ that do not include $x$ as one of the $v_k$ in the sum are exactly the elements of $\mathcal H(V)$, so $\mathcal H(V)\subseteq \mathcal H(V\cup\{x\})$. Further, if $v = \sum_{k=0}^n a_kv_k \in \mathcal H(V\cup\{x\})$ with $v_0 = x$, $v_k \in \mathcal H(V)$ for all $k > 0$, and $a_0 \ne 1$, we can rewrite the sum as $$v = a_0x + (1 - a_0)\sum_{k=1}^n \dfrac{a_k}{1-a_0}v_k$$ and note that $$\sum_{k=1}^n \dfrac{a_k}{1-a_0} = \dfrac 1{1-a_0}\sum_{k=1}^n a_n = \dfrac 1{1-a_0}(1-a_0) = 1$$ since $\sum_{k=0}^n a_n = 1$. So $w = \sum_{k=1}^n \frac{a_k}{1-a_0}v_k \in \mathcal H(V)$ and $v = a_0x + (1-a_0)w$ is a point on the line segment connecting $x$ and $w$. Thus $\mathcal H(V\cup\{x\}) \subseteq H$.

Conversely, if $v\in H$, then there exists a $t \in [0,1]$ and a $w \in \mathcal H(V)$ such that $v = tx + (1-t)w$. Now by definition, $w = \sum_{k=1}^n a_kv_k$ with all $v_k \in V$ and $\sum_{k=1}^n a_k = 1$. Let $v_0 = x, b_0 = t$ and for all $k > 0, b_k = (1-t)a_k$. Then

$$\begin{align}v &= tx + (1-t)w\\&= tx + \sum_{k=1}^n (1-t)a_kv_k\\&=b_0v_0 + \sum_{k=1}^n b_kv_k=\sum_{k=0}^n b_kv_k\end{align}$$ And $$\sum_{k=0}^n b_k = b_0 + \sum_{k=1}^n b_k = t + (1-t)\sum_{k=1}^n a_k = t + (1-t)1 = 1$$ Hence $v \in \mathcal H(V\cup\{x\})$. Since $\mathcal H(V\cup\{x\}) \subseteq H$ and $H \subseteq \mathcal H(V\cup\{x\})$, the two are equal, as required.

Now given any finite set $V = \{v_0, \ldots, v_N\}$, we can set $V_n = \{v_0, \ldots v_n\}$ for all $n \le N$. Since $V_0$ consists of a single point, it is trivially convex, so $C(V_0) = V_0$. But also by the definition, $\mathcal H(V_0) = V_0$. In particular, $C(V_0) = \mathcal H(V_0)$.

But then $C(V_1)$ and $\mathcal H(V_1)$ are both the union of all line segments connecting $v_1$ to elements of $V_0$, and thus are equal as well. Continuing inductively $C(V_n) = \mathcal H(V_n)$ for every $n$.