5

我已经查看了谷歌和堆栈，但还没有找到这个问题的答案。我一直在寻找与单纯形法相关的结果或寻找最小任意单纯形的结果（即顶点不受约束）。我也想不出一个分析解决方案。

给定一组 N 维点M和任意 N 维点q ，如果S的顶点必须在M中，我如何找到包含q作为内部点的最小 N 维单纯形S ? 我确信我可以通过优化来解决它，但如果可能的话，我想要一个分析解决方案。确定性算法也可以。

我最初使用的是 K 最近邻方法，但后来我意识到 q 的 N+1 最近邻不一定会创建包含q的单纯形。

提前感谢您提供的任何帮助。

4

1 回答 1

1

我认为你可以使用与 K-NN 非常相似的迭代过程来做到这一点 O(N^2)，但也许有更有效的方法。这应该返回顶点数的最小单纯形。

对于q中的每个坐标i，我们可以遍历M的所有元素，比较 q_i和m_i。我们将选择M中给出最小正差和最小负差的两个点。如果我们对每个坐标重复这个过程，那么我们应该有我们的最小值集S。

我是否正确理解了这个问题？

于 2016-06-22T22:21:16.693 回答