5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – j_random_hacker Mar 14 at 9:53
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Mar 14 at 10:14
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.