2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.