Smallest convex set containing given point Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is there an (efficient) algorithm that finds $n+1$-subset of $M$ with smallest convex hull that contains $x$ (or, $k$-subset for some $k &lt; n + 1$ if such exists)? "Smallest" is defined according to the volume in $R^n$ (or $R^{k-1}$). "Efficient" would imply something much better than the brute force strategy that examines all $n+1$-subsets of $M$.
Here is an idea to find a "smallish" simplex containing your given point $x$. It does not find a smallest simplex (except by luck).

Construct the convex hull $H$ of your set of $M$ points.
For each $p$ of your set $M$, shoot a ray from $p$
through $x$ until it hits a facet $F$ of $H$. Then $F \cup p$ is a simplex containing $x$. Repeat for all $p \in M$ and retain the smallest volume simplex.

It is easy to create examples where this is terrible, as it is biased toward a simplex
containing a facet of the hull. One can imagine various heuristics to improve, for
example, discarding from $M$ the vertices of $H$ and repeating.