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

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.

• Let me try to understand. You're given a set of vertices $\{v_i\} \subset \Bbb R^D$, as well as a point, $p \in \Bbb R^D$. Presumably, $p$ is inside the convex hull of $\{v_i\}$ (a polytope), which I would write as $p \in \operatorname{conv}(\{v_i\})$. Your question, then, is: How can I find $S \subseteq \{v_i\}$ with minimal cardinality, such that $p$ is still in the convex hull $\rm{conv}(S)$? – pjs36 Mar 26 '15 at 20:35
• You might want to at least add something along those lines to your question; some parts don't make a lot of sense, like saying a polytope $P$ is a subset of a set of discrete vertices $\{v\}$; that's why I wanted to make sure I understood. As far as the existence of $S$: If $p$ really is in the convex hull of $\{v_i\}$, then such a set $S \subseteq \{v_i\}$ is guaranteed to exist, it just might not be a proper subset of the vertices, or be unique (but its size is). Is $p$ guaranteed to be in the convex hull, in your setup? – pjs36 Mar 26 '15 at 22:58
• I relaxed the definition of the proper hull, added the existence condition you mentioned, and removed any requirement of uniqueness. – Leo Mar 27 '15 at 23:01
• I've been thinking about the problem a bit more. I will hopefully be able to write something up in a little while (a few hours to a day or so). – pjs36 Mar 27 '15 at 23:40
• Have you checked whether Delaunay triangulation might help you? If so, CGAL would do the job for you (doc.cgal.org/latest/Manual/…) – Willem Hagemann Apr 15 '15 at 14:05