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.

gibbled
  • 69
  • 3
  • Thanks for pointing that out. I've edited it. – gibbled Nov 07 '15 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? – arghbleargh Jun 15 '16 at 04:37

1 Answers1

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?

Alharithi
  • 39
  • 1
  • 4