For my current research project, I wanted to understand how the points in the interior of the convex hull of a finite number of points changes under perturbation of these points. More specifically, I wanted a statement of the form: Given a point in the interior of the convex hull, this will stay in the interior of the convex hull of any small perturbation of the vertices. In this short note, I will prove a precise statement of this sort.
We work with points in \(\mathbb{R}^q\). The idea is to build a family of perturbations that submerses over \(\mathbb{R}^{q}\). Then we use this submersion to find new "barycentric" coordinates for a point relative to the perturbed vertices.
The first step in this is describing the points in the interior of the convex hull in a suitable way.
Let \(x_1,\ldots,x_m \in \mathbb{R}^q\) and let \(y \in \mathrm{IntConv}(\{x_1,\ldots,x_m\})\). Then there exist \(t_j \in (0, 1)\) for \(1 \le j \le m\) such that \(\sum_{j = 1}^m t_j = 1\) and
\begin{equation*} y = \sum_{j = 1}^m t_jx_j. \end{equation*}Proof.
There is a subtlety we get out of the way first, namely the possibility that \(y = x_j\) for some \(1 \le j \le m\). In that case, we have
\begin{equation*} \mathrm{IntConv}(\{x_1,\ldots,x_m\}) = \mathrm{IntConv}(\{x_1,\ldots,x_m\} \setminus \{x_j\}). \end{equation*}So to deal with this problem, we proceed by induction on \(m\). Since we have assumed (tacitly) that \(\mathrm{IntConv}(\{x_1,\ldots,x_m\}) \not= \emptyset\), we know that \(m \ge q + 1\), since the interior for \(m \le q\) is empty for dimensional reasons. Therefore, our base case is \(m = q + 1\).
Base case: Suppose \(m = q + 1\). Again for dimensional reasons, we must have that \(\{x_1,\ldots,x_{q + 1}\}\) is affinely independent, so that \(\mathrm{Conv}(\{x_1,\ldots,x_{q + 1}\})\) is a \(q\)-simplex. It is a standard result in convex geometry that the lemma is true in this case, see for example (Hug and Weil 2020 Proposition 1.1)
Induction case: Let \(m > q + 1\) and assume that the lemma is true for \(m - 1\). If \(y = x_i\) for some \(1 \le i \le m\). Without loss of generality, we may assume \(i = m\). Then we have
\begin{equation*} \mathrm{IntConv}(\{x_1,\ldots,x_m\}) = \mathrm{IntConv}(\{x_1,\ldots,x_{m - 1}\}). \end{equation*}By the induction hypothesis, we can find \(t_j \in (0, 1)\) for all \(1 \le j \le m - 1\) such that \(\sum_{j = 1}^{m - 1} t_j = 1\) and \(\sum_{j = 1}^{m - 1} t_jx_j = x_m\). From this it follows that
\begin{equation*} x_m = \sum_{j = 1}^{m - 1} \frac{t_j}{2}x_j + \frac{1}{2}x_m, \end{equation*}and so the claim follows in this case.
Now for the general situation, since \(y \in \mathrm{IntConv}(\{x_1,\ldots,x_m\})\), we have \(s_j \in [0, 1]\) for \(1 \le j \le m\) such that \(\sum_{j = 1}^m s_j = 1\) and \(\sum_{j = 1}^m s_jx_j = y\). Let \(I = \{j \mid s_j = 0\}\). We proceed by induction on \(n = |I|\).
Base case: If \(n = 0\), then \(s_j > 0\) for all \(1 \le j \le m\). Then the condition \(\sum_{j = 1}^m s_j = 1\) forces that also \(s_j < 1\) for all \(1 \le j \le m\). So \(s_j \in (0, 1)\) for all \(1 \le j \le m\) and we are done.
Induction case: Suppose that for all possible coefficients yielding \(y\) with \(|I| = n\), the lemma is true. Suppose \(|I| = n + 1\). Let \(j_0 \in I\). We will find new coefficients such that in addition to the coefficients that are already non-zero, we also have non-zero \(x_{j_0}\)-coefficient. The idea is to push the presentation for \(y\) a bit and counteract this pushing by adding a small parameter in front of \(j_0\). This will give a presentation where the \(x_{j_0}\)-coefficient is non-zero. Then adding the two presentations of \(y\) with weight \(\frac{1}{2}\) we get a new convex combination where one more coefficient is non-zero. The proof is then complete by the induction hypothesis. The technical details follow below.
Since \(y\) lies in the interior of the convex hull, we can find \(\varepsilon > 0\) such that
\begin{equation*} y' = (1 + \varepsilon)y - \varepsilon x_{j_0} \in \mathrm{IntConv}(\{x_1,\ldots,x_m\}). \end{equation*}Then there exists \(u_j \in [0, 1]\) for \(1 \le j \le m\) such that \(\sum_{j = 1}^m u_j = 1\) and \(y' = \sum_{j = 1}^m u_jx_j\). Then we have
\begin{equation*} y = \frac{1}{1 + \varepsilon}y' + \frac{\varepsilon}{1 + \varepsilon}x_{j_0} = \sum_{\substack{j = 1\\ j \not= j_0}}^m \frac{u_j}{1 + \varepsilon}x_j + \left( \frac{u_{j_0}}{1 + \varepsilon} + \frac{\varepsilon}{1 + \varepsilon} \right)x_{j_0}. \end{equation*}So we get
\begin{equation*} y = \sum_{\substack{j = 1 \\ j\not= j_0}}^m \underbrace{\left( \frac{s_j}{2} + \frac{u_j}{2(1 + \varepsilon)} \right)}_{=: t_j}x_{j} + \underbrace{\frac{1}{2}\left( \frac{u_{j_0}}{1 + \varepsilon} + \frac{\varepsilon}{1 + \varepsilon} \right)}_{=: t_{j_0}}x_{j_0}. \end{equation*}Then we see that if \(s_j > 0\), it follows that \(t_j > 0\) as well. In addition, since \(\varepsilon > 0\), we also have \(t_{j_0} > 0\). So we have \(I' = \{j \mid t_j = 0\} = I \setminus \{j_0\}\). Then by the induction hypothesis, a convex combination as asserted exists. This completes the proof.
We define the set
\begin{equation*} \Delta_{\mathrm{int}}^m = \left\{(t_1,\ldots,t_m) \in (0, 1)^m \,\middle|\, \sum_{j = 1}^m t_j = 1 \right\}. \end{equation*}This is an (open) manifold. Given \(x_1,\ldots,x_m \in \mathbb{R}^q\) such that \(\mathrm{IntConv}(\{x_1,\ldots,x_m\})\) is non-empty, we have a map \(F\colon \Delta_{\mathrm{int}}^m \rightarrow \mathbb{R}^q\) given by \(F\left(\vec{t}\right) = \sum_{j = 1}^m t_j x_j\). Then the lemma above implies that
\begin{equation*} F(\Delta_{\mathrm{int}}^m) = \mathrm{IntConv}(\{x_1,\ldots,x_m\}). \end{equation*}We will use this result to prove the following stability result.
Let \(x_1,\ldots,x_m \in \mathbb{R}^q\) and \(z \in \mathrm{IntConv}(\{x_1,\ldots,x_m\})\). Then there exist \(\varepsilon, \delta > 0\) such that for all \(y_j \in \mathbb{R}^q\) with \(\|x_j - y_j\| < \delta\) for \(1 \le j \le m\), we have
\begin{equation*} B_{\varepsilon}(z) \subset \mathrm{IntConv}(\{y_1,\ldots,y_m\}). \end{equation*}Proof.
Since \(\mathrm{IntConv}(\{x_1,\ldots,x_m\}) \not= \emptyset\) the vectors \(x_j - x_1\) for \(2 \le j \le m\) are linearly spanning all of \(\mathbb{R}^q\).
We define a map
\begin{equation*} \tilde{F}\colon (\mathbb{R}^q)^m \times \Delta_{\mathrm{int}}^m \rightarrow (\mathbb{R}^q)^m \times \mathbb{R}^q, \left(\vec{y}, \vec{t}\right) \mapsto \left( \vec{y}, \sum_{j = 1}^m t_jy_j \right). \end{equation*}The differential of this map is given by
\begin{equation*} T_{\left( \vec{y}, \vec{t} \right)}\tilde{F} = \begin{pmatrix} I_{mq} & 0 \\ T & X \end{pmatrix}; \quad T = \begin{pmatrix} t_1 I_q & \cdots & t_m I_q \end{pmatrix}; \quad X = \begin{pmatrix} x_2 - x_1 & \cdots & x_m - x_1 \end{pmatrix}. \end{equation*}By the observation at the start of the proof, we see that \(X\) is of full rank, and hence \(TF\) is a submersion at \(\left( \vec{x}, \vec{t} \right)\) for all \(\vec{t} \in \Delta_{\mathrm{int}}^m\).
By Lemma 1, there is a \(\vec{t} \in \Delta_{\mathrm{int}}^m\) such that \(F \left( \vec{x}, \vec{t} \right) = z\). Since \(F\) is a submersion at this point, we can find a local section \(s\colon U \rightarrow (\mathbb{R}^q)^m \times \Delta_{\mathrm{int}}^m\) of \(\tilde{F}\) such that \(s \left( \vec{x}, z \right) = \left( \vec{x}, \vec{t} \right)\), for some open neighbourhood \(U \subset (\mathbb{R}^q)^m \times \mathbb{R}^q\) of \(\left( \vec{x}, z \right)\). Then we can find \(\varepsilon, \delta > 0\) such that
\begin{equation*} B_{\delta}(x_1) \times \cdots \times B_{\delta}(x_m) \times B_{\varepsilon}(z) \subset U. \end{equation*}We claim that these \(\varepsilon, \delta\) satisfy the conclusion of the theorem. Let \(\vec{y}\) be such that \(\|y_j - x_j\| < \delta\). Then we have
\begin{equation*} \left\{\vec{y}\right\} \times \mathrm{IntConv}(\{y_1,\ldots,y_m\}) = \tilde{F}\left( \vec{y}, \Delta_{\mathrm{int}}^m \right) \end{equation*}by the observation above. Now let \(w \in B_{\varepsilon}(z)\). Then we have \(\left( \vec{y}, z \right) \in B_{\delta}(x_1) \times \cdots \times B_{\delta}(x_m) \times B_{\varepsilon}(z)\), and so we get
\begin{equation*} w = \mathrm{pr}_2 \circ \tilde{F} \left( s \left( \vec{y}, w \right) \right) \in \mathrm{IntConv}(\{y_1,\ldots,y_m\}). \end{equation*}So \(B_{\varepsilon}(z) \subset \mathrm{IntConv}(\{y_1,\ldots,y_m\})\), completing the proof.