performance - 批量包含查询

Question

我有一个由一组顶点定义的凸形。我也有大量的点，我想测试包含在凸形中的点。目前，我只是为每个点独立使用开源线性规划求解器，并具有恒定的目标函数。有关详细信息，请参阅http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf的第 11.4 章。

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

编辑有问题的固定错字。

Answer 1

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

拥有船体后，您应该能够相对较快地将所有其他点分类为在船体内部或外部。我确信有算法可以相当快地做到这一点，尽管我不知道。一种可以去除大量内部点的潜在有用方法是：如果空间是 n 维的，则在外壳上选择 n+1 个点并测试每个点以查看它是否是这些点的凸组合（使用线性代数）。