我已经在谷歌和Stack中搜索了很久，但还没有找到解决这个问题的答案。我一直找到与单纯形法相关的结果或者是寻找最小任意单纯形的结果（即顶点没有约束）。我也想不到一个解析解。
给定一组N维点M和任意N维点q，如果要求S的顶点必须在M中，如何找到包含q为内部点的最小N维单纯形S？ 如果可能的话，我希望找到一个解析解。确定性算法也可以。
我最初使用了K近邻方法，但后来意识到，离q最近的N+1个近邻未必能创建一个包含q的单纯形。
非常感谢提供的任何帮助。
如何从一组点中找到包含给定点的最小N维单纯形？
6
- gibbled
2
谢谢指出。我已经编辑了它。 - gibbled
“最小单纯形”是指体积最小，还是其他什么？顺便说一句，这似乎是一个困难的问题；您是否考虑了N和M的特定值或值范围？ - arghbleargh
1个回答
2
我认为您可以使用迭代过程来解决这个问题，时间复杂度为 O(N^2)，非常类似于K-NN，但也许有更有效的方法。这应该会返回最小的单纯形，并且顶点数量也将最少。
对于q中的每个坐标i，我们可以遍历M中的所有元素，比较q_i和m_i。我们将选择在M中给出最小正差异和最小负差异的两个点。如果我们针对每个坐标重复此过程，那么我们就应该得到我们的最小集合S。
我是否正确理解了这个问题？
- Alharithi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接