Find those values 'a' which belongs to the Convex Hull

104 Views Asked by At

Find those values of 'a' for which (1,a,1) belongs to the convex hull of

$$\{(0,0,0), (1,1,2),(2,4,-6), (1,3,8)\}$$

Give me hints as much as you can, I would like to understand the mindset rather than the mechanical way of solving it. Thank you in advance!

1

There are 1 best solutions below

3
On

It's fairly easy to see that the plane $x=1$ cuts the tetrahedral solid generated by $\{(0,0,0),(1,1,2),(2,4,-6),(1,3,8)\}$ in a triangular section with vertices $(1,1,2),(1,2,-3),(1,3,8)$.

The plane $z=1$ then cuts this triangle along a line segment with an endpoint between the first and second of these vertices:

$$ \frac{4}{5} \cdot (1,1,2) + \frac{1}{5} \cdot (1,2,-3) = (1,\frac{6}{5},1) $$

and another endpoint between the second and third vertices:

$$ \frac{7}{11} \cdot (1,2,-3) + \frac{4}{11} \cdot (1,3,8) = (1,\frac{26}{11},1) $$

Thus "by inspection" the feasible interval for $a$ is:

$$ \frac{6}{5} \le a \le \frac{26}{11} $$

We could alternatively formulate the problem as a pair of linear programs, seeking the minimum (resp. maximum) value of $a$ such that:

$$ (1,a,1) = b\cdot (1,1,2) + c\cdot (2,4,-6) + d\cdot (1,3,8) $$

$$ b + c + d \le 1 $$

subject to $b,c,d \ge 0$ nonnegativity constraints. The barycentric coordinates of $(1,a,1)$ with respect to vertices $(0,0,0),(1,1,2),(2,4,-6),(1,3,8)$ are $(1-b-c-d),b,c,d$ respectively.