Plotting some kind of convex hull

Question

I have a set of points $x_i \in \mathbb{R}^2$ and want to plot its convex hull with an additional condition. What I want to plot exactly is: \begin{align} \left\{\sum\limits_i \alpha_i x_i\middle| \sum\limits_i \alpha_i = 1, \ 0 \leq \alpha_i \leq \mu \right\} \end{align} How can I do that? I think it is not possible (in an easy way) in mathematica. I just need some pictures, so it is ok for me if I can only take a very small set.

Answer 1

Let $x_i = (u_i,v_i)$. The desired set of points is the set of the $(u,v) \in \mathbb{R}^2$ that satisfy

$$\begin{align} u &= \sum_i \alpha_i u_i \\ v &= \sum_i \alpha_i v_i \\ 1 &= \sum_i \alpha_i \\ 0 &\leq \alpha_i \leq \mu \enspace. \end{align}$$

Splitting each equality into two inequalities, we get a set of inequalities in $u$, $v$, and the $\alpha_i$'s. If we eliminate the $\alpha_i$'s with, say, Fourier-Motzkin elimination, we obtain constraints on $u$ and $v$ that describe the desired set.

As an example, suppose we are given $$ x_0 = (0,0), x_1 = (1,0), x_2 = (0,1), x_3 = (1,1) \enspace,$$ and $\mu=0.5$. Noting that we can do without $\alpha_0$ if we replace $\sum_i \alpha_i = 1$ with $\alpha_1 + \alpha_2 + \alpha_3 \leq 1$, the initial inequalities are:

$$\begin{align} u &\leq \alpha_1 + \alpha_3 \\ u &\geq \alpha_1 + \alpha_3 \\ v &\leq \alpha_2 + \alpha_3 \\ v &\geq \alpha_2 + \alpha_3 \\ 1 &\geq \alpha_1 + \alpha_2 + \alpha_3 \\ 0 &\leq \alpha_1 \leq \mu \\ 0 &\leq \alpha_2 \leq \mu \\ 0 &\leq \alpha_3 \leq \mu \end{align}$$ For $\mu=0.5$, elimination produces $$\begin{align} 0 \leq u &\leq 1 \\ 0 \leq v &\leq 1 \\ u - v &\leq 0.5 \\ v - u &\leq 0.5 \\ u + v &\leq 1.5 \enspace. \end{align}$$ These inequalities delimit a pentagon, which is easily seen to be the desired set. As expected, the pentagon is entirely contained in the convex hull of $x_0,x_1,x_2,x_3$.