# 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 < 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$$.

• This strikes me as very difficult, even in 2D: it could be that a long, skinny triangle contains $x$ and has lower area than a triangle that uses $x$'s nearest neighbour in $M$. There could be many such triangles with similar area, all having points far from $x$. – j_random_hacker Mar 14 '19 at 9:53
• In 2D it might be possible to get somewhere by relying on the fact that, for an enclosing triangle to have all points far from $x$, at least 2 of those points must be very close together: You could sort all $O(n^2)$ pairs of points by distance, and then for each pair in increasing distance order, look for the best 3rd point in the skinny "pie slice" region on the far side of $x$ that these two points, together with the area of the best solution found so far, imply. But in higher dimensions, a polytope can have all pairs of points "far apart" and still be skinny, so this won't work. – j_random_hacker Mar 14 '19 at 10:14

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.

• In an arbitrary number of dimensions (as in the question), even constructing the convex hull $H$ might be very challenging. – D.W. Mar 14 '19 at 19:10
• @D.W.: Yes, $O(m^{\lfloor n / 2 \rfloor})$. Somewhat better than $\binom{m}{n+1} = O(m^{n+1})$. – Joseph O'Rourke Mar 14 '19 at 21:18