n 個の点がある 2 次元平面が与えられます。片側に n/2 ポイント、反対側に n/2 ポイントがあるように平面を分割する直線の方程式を生成する必要があります。
16247 次
10 に答える
27
私はポイントが明確であると仮定しました、さもなければそのような線さえないかもしれません。
ポイントが異なる場合、そのような線は常に存在し、決定論的なO（nlogn）時間アルゴリズムを使用して見つけることができます。
ポイントがP1、P2、...、P2nであるとします。それらがすべて同じ行にあるわけではないと仮定します。もしそうなら、分割線を簡単に形成できます。
まず、すべての座標（xとy）が正になるように点を変換します。
ここで、y軸上に点Qがあり、それらの点によって形成される線（つまり、無限の線Pi-Pj）がQを通過しないと仮定します。
これで、Qは点の凸包内にないため、Qを通る回転線によって点を並べ替えることができることが簡単にわかります。ある回転角度では、点の半分が片側にあり、残りの半分が残ります。はこの回転線のもう一方にあります。つまり、点が線Pi-Qの傾きでソートされていると考えると、（中央）番目と（中央+1）の間の傾きを選択できます。 thポイント。この選択は、実際にポイントをソートする必要なしに、任意の線形時間選択アルゴリズムによってO（n）時間で実行できます。
次に、点Qを選択します。
Qが（0、b）だったとしましょう。
QがP1（x1、y1）およびP2（x2、y2）と同一線上にあると仮定します。
それから私たちはそれを持っています
（y1-b）/ x1 =（y2-b）/ x2（xi> 0になるようにポイントを変換したことに注意してください）。
bを解くと
b =（x1y2-y1x2）/（x1-x2）
（x1 = x2の場合、P1とP2をY軸上の点と同一線上に配置することはできません）。
|b|を検討してください。
| b | = | x1y2-y1x2 | / | x1 -x2 |
ここで、xmaxを右端の点のx座標とし、ymaxを最上部の座標とします。
また、Dを2つのポイント間のゼロ以外の最小のx座標の差とします（すべてのポイントが同一線上にあるわけではないため、すべてのxiが同じではないため、これが存在します）。
次に、|b|があります。<= xmax * ymax/D。
したがって、点Q（0、b）を|b|となるように選択します。> b_0 = xmax * ymax / D
DはO（nlogn）時間で見つけることができます。
b_0の大きさは非常に大きくなる可能性があり、精度の問題に対処する必要があるかもしれません。
もちろん、より良いオプションはQをランダムに選ぶことです！確率1の場合、必要なポイントが見つかるため、予想実行時間はO（n）になります。
（他の基準を見つけることによって）O（n）時間でQを選択する方法を見つけることができれば、このアルゴリズムをO（n）時間で実行させることができます。
于 2010-06-24T02:17:50.297 に答える
12
その平面に任意の線を作成します。各点をその線上に射影し、その線上でその点に最も近い点を取得します。
線に沿ってこれらの点をいずれかの方向に並べ、線上のいずれかの方向の点の数が等しくなるように、その線上の点を選択します。
その点を通る最初の線に垂直な線を取得します。この線は、両側に元のポイントの半分を持ちます。
これを行う際に避けるべきいくつかのケースがあります。最も重要なことは、すべての点自体が 1 本の線上にある場合、その点を通る垂線を選択しないことです。実際には、その線自体を選択して、ポイントの投影について心配する必要がないようにします。この背後にある実際の数学に関しては、ベクトル射影が非常に役立ちます。
于 2010-06-23T23:45:46.550 に答える
5
これは、点の平面を2つの等しい半分に分割する修正であり、点が重なっている場合を考慮に入れています（この場合、答えが存在するかどうかが示されます）。
If number of points is odd, return "impossible".
Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
(i.e. we pretend this line is our new X'-axis, and write down the
X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
(`O(N)` or faster-if-desired operation)
(returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians
In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).
これはO(N)、他の提案されたソリューションとは異なります。
解決策が存在すると仮定すると、証明はありませんが、上記の方法はおそらく終了します。
重複するポイントを検出しない限り、上記のアルゴリズムを数回試してください。重複するポイントを多数検出した場合は、ラフな乗り心地になる可能性がありますが、考えられるすべての角度をチェックすることを含む、非常に非効率的なブルートフォースソリューションがあります。
For every "critical slope range", perform the above algorithm
by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.
臨界角は、結果を変える可能性のある角度として定義されます（前の答えの解決策を想像し、1つ以上の点が1つ以上の他の点と位置を入れ替えて、分割線を横切るまで、点のセット全体を回転させます。これらの数は限られており、ポイントの数によって制限されていると思います。したがってO(N^2)-O(N^2 log(N))、ブルートフォースアプローチの場合、ポイントが重複している場合は、おそらく範囲内の何かを見ているでしょう。
于 2011-05-10T10:47:19.080 に答える
1
中央値は、達成しようとしているのと同様の方法で一連の数値を均等に分割し、選択アルゴリズムを使用してO（n）時間で計算できます（Cormen et alの記述の方が優れているため、代わりにそこを見てください）。したがって、x値M x（または必要に応じてy値M y ）の中央値を見つけ、 x = M x（またはy = M y）に設定すると、その線は軸方向に整列され、ポイントが均等に分割されます。
問題の性質上、線上に1つの点しか存在しないことが必要な場合（セットに奇数の点がある場合は、少なくとも1つが線上にあります）、それが起こっていることを発見します（または可能性を防ぎたいだけです）、すべてのポイントをランダムな角度θだけ回転させ、回転したポイントの中央値を計算します。次に、計算した中央線を-θで回転すると、ポイントが均等に分割されます。
問題が再び現れるようにθをランダムに選択する可能性は非常に小さく、点の数は有限ですが、そうなる場合は、別のθで再試行してください。
于 2010-06-24T02:18:44.073 に答える
1
良い方法は、ポイントを並べ替え/順序付け/順序付け (たとえば、左から右へ) してから、シーケンスの中間点を通る (またはその間を) 線を選択することだと思います。
于 2010-06-23T23:40:42.210 に答える
1
解決できない明らかなケースがあります。たとえば、ポイントが 3 ヒープある場合などです。場所 A で 1 点、場所 B で 2 点、場所 C で 5 点。
適切な分布が期待される場合は、tlayton のアルゴリズムでおそらく良い結果が得られます。最初の線の傾斜を選択するには、ポイント セット全体の範囲を決定し、最大の対角線の角度を選択します。
于 2010-06-23T23:53:25.260 に答える
1
これが私がこの問題にアプローチする方法です（nが偶数で、3つの点が同一線上にないという仮定で）：
1) Y 値が最小の点をピックアップします。点Pとしましょう。
2) この点を新しい原点として、この変換後に他のすべての点が正の Y 値を持つようにします。
3) 1 つおきのポイント (n - 1 ポイントが残っています) については、極座標系で考えます。他の各ポイントは、半径と角度で表すことができます。半径を無視して、角度だけに集中できます。
4) 点を均等に分割する線をどのように見つけることができますか? (n - 1) 角の中央値を求めます。点 P からその中央角の点までの線は、点を均等に分割します。
このアルゴリズムの時間計算量は O(n) です。
于 2013-08-03T13:27:17.583 に答える
0
Mの答えに追加するには：Q（それほど遠くない）を生成する方法O(n log n).
まず、Q をy 軸上の任意の点とします。Q = (0,b)- (0,0) または (0, (y max -y min )/2) が適切な選択肢です。
ここで、Q と同一線上にある 2 つの点 (x 1 , y 1 )、(x 2 , y 2 ) があるかどうかを確認します。任意の点と Q の間の線はy = mx + bです。b は一定であるため、2 つの点の傾きmが等しい場合、これらの点は Q と同一線上にあることを意味します。したがって、すべてのポイント の勾配 m iを決定し、重複があるかどうかを確認します: (O(n)ハッシュ テーブルを使用して償却)
すべての m が異なる場合、完了です。Q が見つかり、上記の M のアルゴリズムは段階的に線を生成しO(n)ます。
2 つの点が Q と同一線上にある場合、Q をわずかな量 ε だけ上に移動し、 Q new = (0, b + ε)、Q newが他の 2 つの点と同一線上にないことを示します。
以下で導き出される ε の基準は次のとおりです。
ε < m minΔ *x min
まず、m は次のようになります。
m i = y i /x i - b/x i
任意の 2 つの異なるm iの間の最小差を見つけて、それを m minΔ と呼びましょう(たとえば、並べ替えてから、すべての iについて m iとi+1O(n log n) の差を比較します)。
b を ε だけごまかすと、m の新しい方程式は次のようになります。
m i,new = y i /x i - b/x i - ε/x i
= m i,old - ε/x i
ε > 0 および x i > 0 であるため、すべての m が削減され、すべてが最大 ε/x minだけ削減されます。したがって、
ε/x min < m minΔ、つまり ε < m minΔ *x min
が真の場合、以前は等しくなかった 2 つの m iが等しくないことが保証されます。
あとは、m 1,old = m 2,oldの場合、m 1,new =/= m 2,new であることを示すだけです。両方の m iが量 ε/x iだけ減らされたので、これは x 1 =/= x 2を示すことと等価です。それらが等しい場合、次のようになります。
y 1 = m 1、古いx 1 + b = m 2、古いx 2 + b = y 2
すべての点が異なるという仮定に反します。したがって、m 1、new =/= m 2、new、および no 2 点は Q と同一線上にあります。
于 2010-06-24T21:12:53.790 に答える
0
私は Moron と andand からアイデアを受け取り、決定論的な O(n) アルゴリズムを形成し続けました。
また、ポイントは明確で、n は偶数であると仮定しました (分割線上に 1 つのポイントがある不均等な n もサポートされるように、アルゴリズムを変更できると考えました)。
アルゴリズムは、それらの間の垂直線でポイントを分割しようとします。これは、中央の点の x 値が同じ場合にのみ失敗します。その場合、アルゴリズムは、左と下のサイトに同じ x 値を持つポイントがいくつある必要があるかを判断し、それに応じてラインを回転させます。
例を挙げて説明しようと思います。平面上に 16 個の点があるとします。まず、x 値が 8 番目に大きい点と x 値が 9 番目に大きい点を取得する必要があります。別の回答で指摘されているように、選択アルゴリズムを使用すると、これは O(n) で可能です。そのポイントの x 値が異なる場合は、完了です。その 2 つの点の間に垂直線を作成し、点を均等に分割します。
問題は、x 値が等しい場合です。したがって、3 セットのポイントがあります。左側 (x < x a )、中央 (x = x a )、右側 (x > x a ) です。ここでの考え方は、左側のポイントを数え、中央からそこに行く必要があるポイントの数を計算して、ポイントの半分が左側にあるようにすることです。左側に点の半分がある場合、半分以上は右側になければならないため、ここでは右側を無視できます。
では、左側に 3 つのポイント (c=3)、中央に 6 つ、右側に 7 つのポイントがあると仮定しましょう (アルゴリズムは、中央または右側からのカウントを認識していないため、必要ですが、O(n) で決定することもできます)。左サイドに行くには、中央から 8-3=5 ポイントが必要です。最初のステップで既に取得したポイントは、x 値によってのみ決定され、中間の任意のポイントになる可能性があるため、現在は役に立ちません。
中央から 5 つの点が必要で、左側に最小の y 値があり、右側に最大の y 値がある点が必要です。再び選択アルゴリズムを使用して、5 番目に大きい y 値を持つポイントと 6 番目に大きい y 値を持つポイントを取得します。両方の点の x 値は x aに等しくなります。そうでなければ、垂直線が存在するため、このステップに到達しません。
これで、その 2 つの点の中間に点 Q を作成できます。これは、結果の行からの 1 つのポイントです。左側または右側からのポイントが分割されないように、別のポイントが必要です。その点を取得するには、左側からの点が必要です。これは、 x aの垂直線と、その点と Q によって決定される線との間の角度 (b h ) が最も小さい 点です。右側からのその点も必要です (角度 a g )。新しい点 R は、より低い角度の点と垂直線上の点との間にあります (より低い角度が左側にある場合は Q の上の点、より低い角度が右側にある場合は Q より下の点)。
Q と R によって決定される直線は、両側の点が偶数になるように中央の点を分割します。左側または右側のポイントを分割しません。分割すると、そのポイントの角度が小さくなり、R を計算するために選択されるからです。
O(n) でうまく機能するはずの数学者の観点から。コンピュータ プログラムの場合、精度が問題になるケースを簡単に見つけることができます。4 ポイントの例は、A(0, 100000000)、B(0, 100000001)、C(0, 0)、D(0.0000001, 0) です。この例では、Q は (0, 100000000.5)、R (0.00000005, 0) になります。これにより、左側に B と C、右側に A と D が表示されます。ただし、丸め誤差のために、A と B の両方が境界線上にある可能性があります。または、そのうちの1つだけかもしれません。したがって、このアルゴリズムが要件に適合する場合、それは入力値に属します。
-
x 値に基づく中央値である 2 つの点 P a ( x a , y a ) と P b (x b , y b )を取得します。
> O(n) - if x a != x b
その2点間のy軸平行線が結果であるため、ここで停止できます> O(1) - x 値が x aに等しいすべてのポイントを取得します
> O(n) - x の値が x aより小さい点をc として数える
> O(n) - 3 の点の y 値に基づい て最低点 P cを取得します。
> O(n) - 3 の点の y 値に基づい て最大点 P dを取得します。
> O(n) - 3 の点の y 値に基づいて 、(n/2-c) 番目に大きい点 P eを取得します。
> O(n) - また、3 からのポイントの y 値に基づいて 、次に大きいポイント P fを取得します。
> O(n) - P eと P fの間に新しい点 Q (x a , (y e +y f )/2) を作成する
> O(1) - すべての点 P i
について 、P c、Q およびPiの間の角度 a iと、P d、Q および Piの間 の角度 b iを計算します。
> O(n) - 最小角度 a g (a g >0° および a g <180°) を持つ点 P gを取得します。
> O(n) - 最小角度 b h (b h >0°、b h <180°)を持つ点 P hを取得します。
> O(n) - P gまたは P hが存在しない場合(すべての点が同じ x 値を持つ)、どこかに
新しい点 R (x a +1, 0) を作成しますが、x aとは異なる x 値を持ちます
。h P cと P gの間 に新しい点 R ((x c +x g )/2, (y c +y g )/2) を作成する それ以外の場合 は、新しい点 R ((x d +x h )/2, (y d +y h )/2) P dと P hの間
> O(1) - Q と R によって決定される線が点を分割します
> O(1)
于 2010-06-24T16:13:33.557 に答える
0
これがどれほど役立つかはわかりませんが、同様の問題を見てきました...
すでに方向ベクトル（別名、平面の次元の係数）がある場合。
次に、その平面内の 2 つの点を見つけることができ、中点の公式を使用するだけで、その平面の中点を見つけることができます。
次に、その平面と中点の係数を使用して、平面の一般方程式を使用して、両方の点から等距離にある平面を見つけることができます。
線は、一方の変数を他方の変数に関して表現することになるため、両方の平面間の距離が等しい線が見つかります。
平面からの距離方程式を使用した射影など、これを行うにはさまざまな方法がありますが、それはあなたの数学を非常に複雑にすると思います.
于 2010-06-24T00:08:29.610 に答える