Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

Given a set of N-dimensional points, M, and an arbitrary N-dimensional point, q, how do I find the smallest N-dimensional simplex, S, that contains q as an interior point if the vertices of S must be in M? 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.

I was originally using a K nearest neighbors approach, but then I realized it's possible that the N+1 nearest neighbors to q won't necessarily create a simplex that contains q.

Thanks in advance for any assistance provided.

like image 219
gibbled Avatar asked Nov 10 '22 02:11

gibbled


1 Answers

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

For each coordinate i in q, we can iterate through all elements of M, comparing the q_i and m_i. We will select the two points in M which give us the min positive difference and min negative difference. If we repeat this process for every coordinate, then we should have our min set S.

Am I understanding the problem correctly?

like image 87
Alharithi Avatar answered Nov 15 '22 07:11

Alharithi