グラフには、三角形のストリップの問題があります。基本的に、隣接する三角形のセットがあり、各三角形を新しい頂点と見なし、後ろの2つの三角形に共通のエッジがある場合、2つの新しい頂点の間にエッジがあります。
ここでの私の質問は、各三角形を読み取り、それらの新しいストリップグラフを作成することです。
たとえば、次の三角形（A、B、C）があります。
A-0、1、3
B-1、2、3
C-2、3、4
したがって、AとBには共通のエッジがあり、BとCにも共通のエッジがあります。新しいストリップはAからBに移動し、次にCに移動します。
Ok。ここで重要なことの1つは、新しい三角形を読み取るたびに、どの三角形が新しい三角形と共通のエッジを持っているかを知りたいということです。
愚かな方法は、すべての古い三角形をスキャンして、それらの3つの頂点を新しいものの頂点と比較することです。2つの頂点が一致する場合、隣接関係があります。
より良い方法（アルゴリズム設計マニュアルで説明）は、三角形の頂点ごとにリストを作成するたびに行うことです。そのリストには、頂点を通過するすべての三角形が含まれています。たとえば、上記の三角形の場合、頂点0には{A}のリストがあり、頂点1には{A、B}のリストがあります。したがって、新しい三角形が来ると、3つの頂点をチェックして見つけようとします。新しいものと2つの共通の頂点を持つ古い三角形。
ここにいくつかの質問があります：
より良い方法は線形ですか？この種の読み取りとグラフの作成の「線形」を定義するにはどうすればよいですか？たとえば、より良い方法では、新しい三角形は古い三角形の3つのリストを通過する必要があります。これは十分に線形ですか？せいぜいすべての古い三角形を読み取るだけなので、線形だと思いました。しかし、私の考えが本当なら、愚かな方法も直線的ですよね？だから私は間違っているかもしれないと思いますが、非常に混乱しています。
さらに良い方法はありますか？これはアルゴリズム設計マニュアルによって物品税として求められており、その物品税は最悪の場合でも純粋な線形アルゴリズムを求めています。
さらに良い方法のための私の解決策は、各頂点のリストを作成する代わりに、各エッジのリストを作成することです。頂点には多くの三角形が通過する可能性がありますが、エッジがある場合、すべての三角形のエッジが互いに交差しておらず、最大でマージされていると仮定すると、最大2つの三角形が通過します（共通）。
次に、各エッジには最大2つのアイテムのリストがあります。新しく来る三角形の場合、最大3つのエッジをチェックする必要があります。上記のより良い方法よりも良いと思います。
私は正しいですか？または私のより良い方法は純粋な最良の線形ソリューションですか？