以下は、careercup.com の Google インタビュー セクションからの質問です。
2 次元空間に 2*n + 3 点があり、共線上に 3 点がなく、円上に 4 点がない
場合、内側に n 個の点、外側に n 個、上に 3 個の点を含む円を見つけるアルゴリズムを考案してください。
私はO（n ^ 4）の解決策を考えることができます：
a）[C（2n + 3,3）の方法で]任意の3点を選び、これら（O（n ^ 3））で円を作ります
b）それぞれについて円、正確に 'n' 個の点がその中にあるかどうかをチェックします O(n)
これは単純なアプローチであるため、この問題にアプローチするより良い方法があるかどうかを尋ねたいと思いますか? つまり、O(n log n) のオーダーの何か
これが O(n) ソリューションです。
S を点の集合とします。p を S の左端の点とします。その場合、p は S の凸包上にあります。q を S の点とし、p から左に向かう光線と、p から始まり q を通る光線との間の角度を最小にします。p と q の両方が O(n) 時間で見つかります。線分 pq は S の凸包のエッジであり、直線 pq の左側に S の点はありません。
セグメント pq の軸 A を取ります。p と q を含む円の中心は、正確に軸 A 上の点です。A 上のすべての点 c について、c を中心とし、p と q を含む円を C(c;p,q) とします。c が A の左に十分離れた点である場合、C(c;p,q) は内部に S の点を持ちません。c が A の十分右にある点である場合、C(c;p,q) は p,q 以外の S のすべての点を内部に持ちます (p と q は円上にあります)。c を左から右に移動すると、S の点は円 C(c;p,q) に 1 つずつ入り、決して離れません。したがって、その中間のどこかに、C(c;p,q) が p,q と S のもう 1 つの点を含み、S の他の点が正確に n 個含まれるような、A 上の点 c があります。
これは、O(n logn) で明確にわかります。 p と q 以外の S のすべての点 s について、C(c;p,q) に p、q、および s が含まれるような A 上の点 c を見つけます。点ｃは、軸Ａと線分ｑｓの軸との交点である。A に沿って移動中に c を通過すると、s は円 C(c;p,q) に入ることに注意してください。これらの中心を x 座標を増やして並べ替え、(n+1)-st を取ります。これは、S のちょうど n 個の点が既に C(c;p,q) 内にあり、p、q、およびもう 1 つの点がオンになっている場合の点です。 C(c;p,q)。O（n）でそれを行うには、すべてをソートせずに（n + 1）-stを見つけます。
この問題を O(n) 時間で解決する簡単な方法は、inversion in a circleを使用することです。
概要
セットから任意の点 O(x,y) を選択して原点とrし、選択した点を中心とする半径の円を選択します。点 O が原点になるように、すべての点が (-x,-y) だけ平行移動すると、計算が簡単になります。
原点と円を選択したら、選択した円に関してセット内の他のすべての点に対して反転操作を実行します。座標では、点 P(x,y) を座標 の新しい点 P' にマップします(x',y') = (x,y)*r^2/(x^2+y^2)。原点 O(0,0) は無限遠点に向かいます。
逆変換を使用すると、問題は必要なプロパティを持つ線を見つけることになります (線は常に無限遠点を通過するため、2 つの変換された点を通過します。さらに、線は残りの変換された点を 2 つの等しいセットに分割する必要があります)。
反転は、3 つの共線ポイントと 4 つの同心ポイントのセットを 3 つの共線ポイントと 4 つの同心ポイントのセットにマッピングすることに注意してください。したがって、変換されたセットには、3 つの共線ポイントと 4 つの同心ポイントはありません。
円を構築するために、逆反転を実行します (円の反転はインボリューション、つまり自己逆変換であるため、元の反転と同じです)。これにより、元のセットから最初に選択された点と他の 2 つの点を通る円に線が引き戻されます。残りの半分は円の内側にあり、半分は外側にあります。
対応する線の問題
ここで、問題を次のように縮小しました: 平面内に 2n+2 点が与えられた場合、残りの 2n 点のうち、n が線の片側にあり、n が反対側にあるような 2 つの点を通る線を見つけます。 .
その質問に O(n) 時間で次のように答えることができます。まず、セットの凸包の境界に 1 つの点が必要です (凸包全体は必要ありません)。このような点 P は、座標の最小 x 値を持つセット内の点を見つけることで見つけることができます。これは、Quickselect アルゴリズムを使用して O(n) 時間で実行できます。
これで、すべてのポイントが P の右側の半空間にあることがわかりました。次のステップのアイデアは、P を通る水平線 h に対するすべてのポイントの中央角でポイント Q を見つけることです。 Quickselect アルゴリズムを使用すると、O(n) 時間で実行できます。同一線上にある 3 つの点はあり得ないので、同じ角度の 2 つの点はあり得ません。
直線 PQ は 2 つの点を通過し、角度 Rph が QPh より大きいか QPh より小さいか (負の角度は h より小さい) に従って、残りの点 R を 2 つの等しい部分に分割します。
小さな問題が 1 つ発生する可能性があります。線分が原点を通過する場合、反転により円ではなく別の線分になります。ただし、元のセットに 3 つの同一線上の点があり、問題ステートメントによってそうではないことが保証されていることを意味するため、そのような状況は発生しません。
理想的な条件では、円の外側に n 個の点、内側に n 個の点があり、その上に 3個の点がある場合、正確にn 個の点の中心からの距離は半径よりも大きく、半径よりも正確にn 個小さい点..そして 3 個の点だけになります。半径に等しい..これは、特定の瞬間に外側/内側にある数をすばやく確認するのに役立ちます..
2D ポイントでボルノイ図を作成します。これは、どのポイントが他のどのポイントに近いかを見つけるのに役立ちます。概念を知る必要がある場合は、検索してください。
隣接する3 点から円を作成することから始めます。この円の中心までのすべての点の距離を配列に格納します。距離が R より大きい点は外側にあり、距離が小さい点は内側にあります。
徐々に、円上の点を残し、円の境界に最も近いが円の外側にある点を選択して、新しい円を作成し、配列を再計算します。
内側の点の数をNin、外側の点の数をNoutと呼ぶと..Noutは減少し始め、Ninはゆっくりと増加し始めます. それらが等しくなるまでこれを続けます（もしそうなら）またはNinがNoutを超えます..これが起こった場合、境界の内側と近くの点を選択して新しい円を作ります. Nin == Nout が得られるまでこれを続けてください。その時点で解決策が得られます..
円の外側に新しい点を取ると円の半径が大きくなり、円の内側に新しい点を取ると半径が小さくなることに注意してください。
これは私の頭に浮かんだ最初のまともな解決策です。これは、特定の側面で改善する必要があるかもしれません。複雑さは、ブルート フォース ソリューションよりもはるかに優れていると思います。計算はお任せします。:)
QuadTreeの使用を検討できます: Quadtree on wiki 次に、この構造を使用して、各ノードの近接をスキャンできます。Query Rangeという機能があるようです。この機能を使用すると、円を徹底的に選択するだけでなく、より正確になると思います。
これは解決策ではなく、開始するための単なるアイデアであることに注意してください。