From a set of vertices, find smallest polytope enclosing another point

Question

Out of a set of vertices $V=\{\vec v_i\in \mathbb R^D\}$, I am constructing a piecewise linear interpolating function $f:\mathbf{conv}(V)\rightarrow R$ as follows: given a point $\vec d\in \mathbf{conv}(V)$, I want to construct the smallest convex hull out of given vertices:

1. a convex hull $H = \mathbf{conv}(P=\{\vec p_i\})$
2. from the given vertices $P=\{\vec p_i\}\subseteq\{\vec v_i\}$,
3. that contains the given point $\vec d\in H$,
4. that does not contain any other given vertices as interior points $\forall \vec v_i, \vec v_i \notin P <=> \vec v_i\notin H$. All points belonging to a face or edge should be included into $P$.
5. It does not have to be of the full dimension $H\subset\mathbb R^d, d \leq D$.

This way, I can guarantee that the interpolation will not "extrapolate" (e.g. yield values $f>\max f(\vec v_i)$ or $f<\min f(\vec v_i)$).

Question: how do I construct such a set in the simplest way? I don't need the computationally optimal, just a reasonable solution. E.g. defining and checking all the possible polytopes seems slow and bug-prone.

Difference from the "classical" convex hull search - It can be defined

• minimal - contains as few of $V$ vertices as possible $\forall \vec p_j\in P,\vec d\notin \mathbf{conv}(P\setminus\{\vec p_j\})$
• maximal - contains as many $V$ vertices as possible, but only as $P$ elements, not interior points

Hopefully, the latter is enough to make the solution unique. Otherwise, any solution will do.

Ideas on solution: It should be useful to sort the vertices by distance from $p$ and take one by one, until the is.complete(polytope), such as in incremental hull construction. Then we may need pruning.

We may need less or more than $D+1$ vertices. As for the criteria, I tried to make sure that for each dimension, there is either 1 vertex with the same coordinate (it will happen in my setup), or 2 vertices with coordinates greater and less than the given. However, for $D=2$, you can try to draw a triangle and see that this is maybe a necessary, but not sufficient criteria.

Another idea is to try projecting $\vec d$ on all possible faces. The projection will fall within all faces of the proper hull.

Disclaimer: a software that does this would also do, but I coudn't find any that seemed to do this.