グラフ内の閉じたセルの識別

Question

ノードは3D空間内の点を表すグラフを持っています。各ノードは、いくつかのカットオフ半径内の他のすべてのノードにのみ接続されています。私はノードが内部ノードもエッジも持たない多面体の頂点を表すようにすべての部分グラフを列挙しようとしています。

私はこれがクリークの問題だと思っていましたが、すべてのノードが互いに隣接しているという要件は私のために働いていません。キューブの反対側のコーナーは私のデータセットでは接続されませんが、キューブを引き出す必要があります。

私は実際にCSで正式な教育を受けていないので、何を検索するのかは分かりませんが、私よりも優れたドメイン語彙を持つ人が正しい方向に向かうことができればうれしいです。

Answer 1

この問題を攻撃する1つの方法は、3D三角形分割「四面体化」を使用するように思えます。 CGALがそこに勤務することができます。次に、三角形分割から隣接する四面体を貼り付けることで、異なる多面体を生成することができます（結合された内部に別の頂点を入れない限り）。