1

ユークリッド空間の点が与えられた場合、任意の超平面の下にある点の数を数える高速なアルゴリズムはありますか? 速いということは、時間計算量が O(n) よりも低いことを意味します

ポイントの前処理またはソートの時間は問題ありません

あと、高次元じゃなくても2次元空間で使えるものがないか知りたいです

4

3 に答える 3

2

ポイントを前処理する場合は、各ポイントに少なくとも 1 回アクセスする必要があります。これは O(n) です。ポイントがどちら側にあるかのテストを前処理の一部として検討する場合、O(0) アルゴリズム (O(n) 前処理を使用) が得られます。したがって、この質問は、述べられているように意味がないと思います。

それにもかかわらず、たとえそれがOPが求めたものでなくても、私は有用な答えを出そうとします.

超平面単位の法線とルート ポイントを選択します。平面がパラメトリック形式で与えられている場合

(P - O).N == 0

法線がユニット化されていることを確認してください。

それが分析形式で与えられる場合: Sum(i = 1 to n: a[i] x[i]) + d = 0 の場合、ベクトル A = (a 1 , ... a[n]) は次の法線です。平面、および N = A/||A|| は単位平面法線です。平面上の点 O (原点) は d N です。

パラメータの符号をチェックして、各点 P を N に射影することにより、各点 P がどちら側にあるかをテストできます。

V = P - O とします。V は、選択した原点 O から P へのベクトルです。

s Nを V の N への射影とします。s が負の場合、P は超平面の「下」にあります。

テーマに慣れていない場合は、ベクトル射影に関するリンクに移動する必要がありますが、ここでは私の表記法を使用して要約します。または、私の言葉を信じて、最後の式にスキップすることもできます.

alpha が V と N の間の角度である場合、コサインの定義から、cos(alpha) = s||N||/||V|| が得られます。= s/||V|| N は単位法線であるためです。しかし、ベクトル代数から、cos(alpha) = ||V||(VN) もわかります。スカラー積 (別名ドット積、またはユークリッド内積) です。

これら 2 つの式を cos(alpha) に等しくすると、次のようになります。

s = (VV)(VN)

(||V||^2 == VV という事実を使用)。

したがって、進行中の作業は N と O を計算することであり、テストは次のとおりです。

bool is_under = (dot(V, V)*dot(V, N) < 0.);

これ以上速くできるとは思えません。

于 2012-08-13T06:13:16.737 に答える
0

ポイント値を設定する場合は、そのポイント設定時のチェック条件を使用してください。次に、カウンターをインクリメントするか、インクリメントしないでください。の上）

于 2012-08-12T16:17:43.323 に答える
0

O(N log N) の前処理時間の複雑さと O(N log N) のメモリの複雑さを伴う分割統治法と二分探索を使用して、2D 次元で O(logN) アルゴリズムを見つけました。

基本的な考え方は、点は左の N/2 点と右の N/2 点に分割でき、線の下にある点の数 (2D 次元で) は、線の下の左の点の数と数の合計です。線の下の右側のポイント。点全体を「左」と「右」に分ける無限の線を「分割線」と呼びます。分割線は「x = k」のようになります

それぞれの「左の点」と「右の点」が y 軸の順序で並べ替えられている場合、特定の点 (右下隅の点) の数は、バイナリ検索を使用してすばやく見つけることができます。線と分割線の交点の y 値よりも低くなります。

したがって、時間複雑度は

T(N) = 2T(N/2) + O(log N)

最後に、時間の複雑さは O(log N) です

于 2012-08-14T07:04:15.113 に答える