How to find the smallest N dimensional simplex from the set of points containing a given point?

Question

I looked at google and the stack, but have not yet found an answer to this problem. I continue to find results related to the simplex method or the results for finding the smallest arbitrary simplex (i.e. vertices are not limited). I also cannot think of an analytical solution.

For a set of N-dimensional points M and an arbitrary N-dimensional point q, how to find the smallest N-dimensional simplex, S , which contains q as an interior point if the vertices S must be in M ? I am sure that I can solve this problem with optimization, but, if possible, I would like to get an analytical solution. The deterministic algorithm will also be in order.

I initially used the K nearest neighbors approach, but then I realized that it is possible that N + 1 nearest neighbors to q will not necessarily create a simplex containing q.

Thanks in advance for your help.

Answer 1

I think you can do this O (N ^ 2) using an iterative process very similar to K-NN, but maybe there is a more efficient way. This should return a minimal simplex in terms of the number of vertices.

For each coordinate i in q, we can iterate over all elements of M by comparing q_i and m_i. We will choose two points in M that give us the minimum positive difference and the minimum negative difference. If we repeat this process for each coordinate, then we must have our minimal set S.

Do I understand the problem correctly?