6

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.

2
  • Thanks for pointing that out. I've edited it.
    – gibbled
    Nov 7, 2015 at 17:28
  • By "smallest simplex", do you mean by volume, or something else? BTW, this seems like a hard problem; do you have in mind specific values or value ranges of N and M? Jun 15, 2016 at 4:37

1 Answer 1

2

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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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