n点が与えられると、それらの3つは同一線上にありません。iとj、直径としてi＆jで形成された円に他の点が含まれていない場合、2点は友達です。O（nlogn）でそのようなすべてのポイントを与える
質問する
703 次
4 に答える
5
あなたは、文献で相対近傍グラフとして知られているものを計算しようとしています。2つのポイントによって決定されるルーンは空でなければなりません。このトピックに関する文献はかなりあります。ウィキペディアの記事から始めることができます。ユーザーtmyklebuが言うように、それはドロネー三角形分割のサブセットです。
訂正。Asiriが親切に説明したように、私は条件を読み間違えました。関連するグラフは、代わりにGabriel Graphであり、これにもかなりの文献があります。
于 2012-12-09T02:51:07.900 に答える
1
Delaunay三角形分割を計算します。2つのポイントが友達である場合、それらはドロネー三角形分割の隣人である必要があります。
ただし、その逆は当てはまりません。Delaunay三角形分割の（線形に多くの）エッジのそれぞれをチェックして、別のポイントが円内にあるかどうかを確認する必要があります。これを行うには、すべてのエッジを繰り返し処理します。現在の反復uとvの終わりを呼び出します。uの近傍は、vから時計回りに列挙できます。a_1をvから時計回りにuの次の隣人とし、a_2をvから反時計回りにuの次の隣人とします。a_1とa_2が、直径がuvの円内にないことを確認するだけです。
于 2012-12-08T22:23:37.097 に答える
0
私はこの答えにあまり自信がありません。間違っている場合は訂正してください。
最初の2つのポイントから開始するため、円は1つだけです。(p1, p2, c, r)この円は、円の中心と半径である場所cで表すことがrできます（これらはオンザフライで計算することもできます）。
次に、必要に応じて新しい円を壊したり作成したりしながら、残りのポイントを段階的に追加します。
したがって、あるステップで、いくつかmの円があり、ポイントを導入しようとしている場合はp、スキャンして、いずれかの円の内側にあるかmどうかを確認します（効率的に与えられて決定できます）。が円の内側にある場合は、その円を破棄して、2つの新しい円を作成します（破棄された円の2つのポイントを使用して）。pcrpp
一方、pすべての円の外側にある場合は、最も近い点を見つけてp新しい円を作成する必要があります。pさて、どうすれば「最も近い点」を効率的に見つけることができるのか完全にはわかりませんが、このようなものかもしれません。
完全に軌道に乗っていない場合はお詫びします！
更新：「に最も近いポイント」が1つ以上ある場合の対処方法がわかりませんp。その数の新しいサークル（？）を作成することができます。
于 2012-12-08T21:55:59.860 に答える
0
以下をドロネー三角形分割に接続します。
最初に定義して、点とD(x,y)の間の距離を示します。xy
プロパティ-I：任意の2つの点p1とが与えられた場合p2、3番目の点p3は円上または円の内側にあり、その直径の1つはとによって形成p1されるセグメントです。p2
D(p1,p3)^2+D(p2,p3)^2<=D(p1,p2)^2.
これは、円の角度が、それが見ている円の部分の半分の角度であり、したがって、直径を見ているものが正しいためです。
したがって、Delaunayタイルで三角形を形成するポイント（最大で2つのそのようなポイント）が両方ともProperty-Iを満たす場合、p1とは友達です。p2
于 2012-12-10T20:13:47.047 に答える