algorithm - O(n log n)の単位正方形で独立した点を見つける方法は?

Question

n 個の 2D 点を含む単位正方形を考えます。2 つの点 p と q は、それらの間のユークリッド距離が 1 より大きい場合、正方形内で独立していると言えます。単位正方形には、最大 3 つの相互に独立した点を含めることができます。O（n log n）の指定された単位正方形で、相互に独立した3つの点を見つけたいと思います。出来ますか？私を助けてください。

この問題は、Quadtree、kd-tree などの空間データ構造を使用せずに O(n^2) で解決できますか?

Answer 1

これは間違った解決策です。コメントのためだけに保管しました。最小の囲み円に基づいて別の解決策を見つけた場合は、リンクをコメントとして入力してください。

---

1. 最小円問題を解きます。

2. 円の直径 <= 1 の場合、null を返します。

3. 円が 3 点で決まる場合、どれが「相互に独立」しているかを確認します。それらが 2 つしかない場合は、繰り返して 3 つ目を見つけてみてください。

4. 円が 2 点で決まる場合、それらは「相互に独立」しています。反復によって 3 番目のものを見つけてみてください。

最小円問題は O(N) で解決できるため、問題全体の複雑さも O(N) になります。

Answer 2

これを試してみてください。

Pick the top left point (Y) with coordinate (0,1). Calculate distance from each point from the List to point Y.
Sort the result in increasing order into SortedPointList (L)
If the first point (A) and the last point (B) in list L are independent:
    Foreach point P in list L:
        if P is independent to both A and B:
             Return A, B, P
Pick the top right point (X) with coordinate (1,1). Calculate distance from each point from the List to point X.
Sort the result in increasing order into SortedPointList (S)
If the first point (C) and the last point (D) in list L are independent:
    Foreach point O in list S:
        if P is independent to both C and D:
             Return C, D, O
Return null