横線上の3点を横切る線を見つける

Question

3点の水平線（y = 0、y = 1、y = 2）上に広がるn点群を考えると は交差線があるかどうかを見つけるアルゴリズムを考えるO（N^2）

enter image description here

Answer 1

私はO（N^2）で、このアルゴリズムを信じています。まず、前提としていますラインy=2上の点の

1. x -coordinatesは有限のビット数で表すことができます。
2. これらのx座標は、最初にxにソートされています。そうでない場合は、最初にソートするのはO（nlog（n））です。
3. クロスラインの定義は、有限のビット数で点を表現する精度に関して行われます。今

次のように、ハッシュ関数を構築する：

1. はラインy=2上の隣接点間の最小距離を検索します。 x - 座標がソートされているので、これはO（n）です。この最小距離dと呼んでください。
2. ハッシュ関数はfloor（2 * x/d）です。このハッシュは、y=2の各点を一意のビンにマップすることは明らかです。この操作もO（n）です。

そして、次の操作を行います。

1. 線y=0とy=1上の点の各ペアについて、y=2上の交差を計算します。これはO（n^2）です。
2. y=2の交点ごとに、そこからの点があるかどうかを調べるためのハッシュテーブルを参照してください。もし存在すれば、それが（機械の精度内で）同じ点であるかどうかを確認し、そうであれば、交差する線がある。それ以外の場合はありません。ハッシュルックアップがO（1）なので、これはO（n^2）です。

したがって、アルゴリズムはO（n^2）です。コードなし、アイデアだけ。