performance - 批量包含查询

Question

我有一个由一组顶点定义的凸形。我还有一大组点，我想测试凸形中包含哪些点。目前，我只是对每个点独立使用一个开源线性规划求解器，目标函数是恒定的。参见 http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf 的第 11.4 章了解更多详情。

然而，即使在 100 个维度上，这也很慢。有没有办法利用预先知道所有查询点的事实来加快处理速度？

编辑 修正了有问题的拼写错误。

Answer 1

我的建议是找到形状内点的凸包。我无法立即想到一种直接从 LP 求解器获得它的方法，但是您可以通过向目标函数添加该超平面的线性项来找到最接近给定形状超平面的点。对形状的所有边重复此操作，并为每个边重复多次，每次都消除最近的解决方案以拾取距离越来越远的包含点。这应该会给您一些“接近”超平面和超平面内部的点。

获得船体后，您应该能够相对快速地将所有其他点分类为在船体内部或外部。我确信有算法可以相当快地完成此操作，尽管我不知道有任何算法。一种可以去除大量内部点的潜在有用方法是:如果空间是 n 维的，则在船体上选取 n+1 个点并测试每个点以查看它是否是这些点的凸组合(使用线性代数)。