title: How to find the smallest N dimensional simplex from a set of points that contains a given point?
body: <p>I've looked all over google and stack but haven't found an answer to this problem yet. I keep finding results relating to the simplex method or results for finding the smallest arbitrary simplex (i.e. the vertices are not constrained). Neither can I think of an analytical solution.</p>
  
  <p>Given a set of N-dimensional points, <strong>M</strong>, and an arbitrary N-dimensional point, <em>q</em>, how do I find the smallest N-dimensional simplex, <strong><em>S</em></strong>, that contains <em>q</em> as an interior point if the vertices of <strong><em>S</em></strong> must be in <strong>M</strong>? I'm sure I could solve it with an optimization, but I'd like an analytical solution if possible. A deterministic algorithm would be ok, as well.</p>
  
  <p>I was originally using a K nearest neighbors approach, but then I realized it's possible that the N+1 nearest neighbors to <em>q</em> won't necessarily create a simplex that contains <em>q</em>.</p>
  
  <p>Thanks in advance for any assistance provided.</p>