I have a set of points ${x_n}_{n=1}^N$ where $x_n in mathbb{R}^D$. I have another vector $y in mathbb{R}^D$. I’d like to efficiently compute the component of $y$ that lives outside the convex hull of the set of points ${x_n}$.

Is this possible, and if so, what algorithms/methods exists for doing so?

To be clear, I do not want to know whether the vector $y$ is inside or outside the convex hull. I want to compute the component of $y$ outside the convex hull. The result should be a vector, not a Boolean.

In case it is helpful, in my setting, $N >> D$.

Related Prior Questions:

• What’s an efficient way to find if a point lies in the convex hull of a point cloud?
• Rough test if points are inside/outside of convex hull