algorithm - 使用 CGAL 求解 LP 可行性

Question

我们能否使用 CGAL 解决以下形式的线性规划可行性问题(如果不能，请提出替代方案):

v.x_a > c 和，

v.x_b = c

其中v,x_a,x_b,c分别是向量，向量，向量和标量。我想为给定的 x 集找到一个元组 (v,c)( x_a 和 x_b 是x) 的元素满足这个不等式。

我看到了 documentation但允许的形式是 Ax(relation operator)b 类型，其中 relation operator 可以是 >=、<= 或 =，其中 A 和b 是已知的，x 是未知的，但我的要求是相反的，即我有 x 但我想确定是否存在元组 (A,b) 满足不等式。

上下文:我正在尝试实现一个 3D 网格生成器，我需要为此测试一条边(连接两个 3D 顶点)是否是 Delaunay。 Delaunay 边 定义为:一条边是 Delaunay，当且仅当存在其端点的外 catch 且其中不包含任何其他顶点。

我的问题是基于描述的方法 here

Answer 1

根据 David Eppstein 在链接问题中描述的结构，i和 j是固定的，我们有额外的限制 v.xi = v.xj = c .所以问题就变成了:

Find a vector v != 0 such that v.xk >= v.xi for all k and v.xi = v.xj.

这可以转化为

Find a vector v != 0 such that (xk - xi).v >= 0 for all k and (xi - xj).v >= 0 and -(xi - xj).v >= 0

通过定义 A作为具有行的矩阵 xk - xi对于所有 k，xi - xj和 xj - xi , 我们得到

Find a vector v != 0 such that Av >= 0

它有你需要的形式。您可以执行 v != 0通过暴力破解非零分量。对于每个组件 i并且，尝试添加条件 vi >= 1或 vi <= -1并检查生成的系统的可溶性。由于平面的法向量可以任意缩放，如果任何生成的程序是可解的(如果 2d 是 d 的维数，则有 v 个解)。