我已经搜索了谷歌和堆栈，但还没有找到这个问题的答案。我一直在寻找与单纯形法有关的结果或寻找最小任意单纯形的结果（即顶点不受约束）。我也想不出一个分析性的解决方案。
给定一组N维点，M和任意N维点q，如果S的顶点必须在M中，我如何找到包含q作为内点的最小N维单纯形？我确信我可以通过优化来解决它，但如果可能的话，我想要一个分析解决方案。确定性算法也可以。
我最初使用的是K近邻方法，但后来我意识到，q的N+1近邻可能不一定会创建包含q的单纯形。
提前感谢您提供的任何帮助。
我认为你可以使用与K-NN非常相似的迭代过程来实现这一点，即O（N^2），但也许有一种更有效的方法。这应该返回顶点数量方面的最小单纯形。
对于q中的每个坐标i，我们可以遍历M的所有元素，比较q_i和M_i中的两个点，这两个点给我们最小正差和最小负差。如果我们对每个坐标重复这个过程，那么我们应该有我们的最小集S。
我对这个问题的理解正确吗？