解決在使用CGAL

Question

我們可以解決以下使用CGAL提到形式線性規劃可行性問題LP可行性（如果沒有，請提出其他建議）：

v.x_a > c和，

v.x_b = c

其中v， x_a，x_b,c分別是矢量，矢量，矢量和標量。我想爲給定的x（x_a和x_b是x的元素）的給定集合找到一個元組(v,c)，它滿足這個不等式。

我已經看到了documentation但容許形式是Ax(relation operator)b其中relation operator可以是> =，< =或=，其中兩個A和b是已知的並且x是未知的，但我的要求是相反的，這是我有x類型的但我想確定是否存在滿足不等式的元組(A,b)。

語境： 我想實現一個3D網格生成的，我需要測試的邊緣（連接兩個3D頂點）是否是德勞內。 Delaunay邊緣被定義爲：邊緣是Delaunay，如果存在其端點不包含任何其他頂點的圓環。

我的問題是基於該方法描述here

Answer 1

據大衛Eppstein的描述中鏈接的問題建設，i和j是固定的，我們有額外的限制，即v.xi = v.xj = c。所以，問題就變成了：

查找所有k和v.xi = v.xj載體v != 0這樣v.xk >= v.xi。

這可以轉化爲

查找矢量v != 0使得(xk - xi).v >= 0對於所有的k和(xi - xj).v >= 0和-(xi - xj).v >= 0

通過定義A作爲基質與對於所有的k行xk - xi， xi - xj和xj - xi，我們得到

查找矢量v != 0這樣Av >= 0

其中有你需要的形狀。您可以強制使用非零組件強制執行v != 0。對於每個組件i，嘗試添加條件vi >= 1或vi <= -1，並檢查生成的系統的可解性。由於飛機的法向矢量可以任意縮放，因此如果得到的任何程序都是可解的（如果d是v的維度，則有2d）。