檢查點集三角形細分是一個三角形

Question

我一直在研究Delaunay triangulation（不是家庭作業），我想到了以下問題：給定一組點S在平面上（基數爲n）和一組三角形T（應與n-2的基數） - 如何確定三角形是否設置爲T形成Delaunay三角剖分DT(S)？

第一個問題是Delaunay三角剖分不是唯一的，因此重建它再次設置點並與三角形集相比較不會給我們答案。另外，最佳的Delaunay三角剖分算法很難實現（然而，使用像CGAL這樣的圖書館可能沒問題）。

假設我們知道如何檢查三角形集是否是三角剖分（不一定是Delaunay）。然後我們應該使用Delanuay三角剖分的定義：對於三角形中的每個三角形t，S中的任何點都嚴格限定在t的圓周內。這導致我們採取以下方法：

1. 平凡的方法。只需遍歷T，計算周長並遍歷S，檢查點是否在圓周內。但是，這需要O(n^2)時間，這不是非常優化的。
2. 迷人的方法。再次重複T並計算周長。如果在圓周內的任何點s，這意味着它到圓周中心的距離小於半徑。使用S的最近鄰搜索結構，我們將加快我們的算法。例如，簡單的kd-tree結構導致我們在O(n log n)算法平均和O(n sqrt(n))在最壞的情況下。
3. 有沒有人有更簡單的想法？

現在讓我們回到檢查T是否是三角測量的問題。像平等S和一組三角形的頂點的平凡預先要求可以執行不快於O(n log n)。還剩下什麼 - 檢查T中的每兩個三角形是相交還是不相交。

1. 同樣，我們可以通過遍歷T，並再次超過T，檢查路口做到這一點，但是這是O(n^2)算法。
2. 讓我們來思考一下«三角形t1和t2相交»是什麼意思？如果它們的邊相交，或者如果一個三角形完全位於另一個三角形中，則它們相交。使用Bentley-Ottmann algorithm（最壞的情況是O((n + k) log n)，其中k是交點的計數，但我們可以在我們找到第一個交點時停止算法）可以在O(n log n)時間解決所有邊相交的問題。我們也沒有認識到一個三角形完全包含另一個三角形的情況，但我相信我們可以修改Bentley-Ottmann算法來維持橫過掃描線而不是段的三角形，正如我所說的那樣，我們可以得到我們的O(n log n)算法。但是，實施起來真的很複雜。
3. 我想過迭代算法 - 讓我們保持非相交（或僅與邊相交）三角形的結構（它應該與kd-tree非常相似）。然後我們嘗試添加下一個三角形t：首先檢查是否有任何t的頂點已經在其中一個三角形中 - 然後我們得到了一個十字路口。否則，將t添加到結構中。但是，如果我們需要O(log n)或O(sqrt(n))時間來進行搜索和添加查詢，我們必須平衡這個結構的高度，即使對於kd樹也是如此。

那麼，有沒有人知道任何簡單的解決這個問題？

Answer 1

有一個德勞內引理：「如果S中三角剖分K中的每條邊都是局部Delaunay，那麼K就是S的Delaunay三角剖分」。也許這可能有助於你的問題的第1段的情況，你可以肯定K是S的一些三角形。不過這種方法的計算複雜性。儘管如此。