如何在O(n log n)中找到单位平方的独立点？

Question

考虑包含n个2D点的单位正方形.如果它们之间的欧几里德距离大于1,我们说两个点p和q在一个正方形中是独立的.单位正方形最多可以包含3个相互独立的点.我想在给定的单位平方中找到O(n log n)中的那3个相互独立的点.可能吗？请帮我.

在不使用任何空间数据结构(如Quadtree,kd-tree等)的情况下,可以在O(n ^ 2)中解决此问题吗？

Answer 1

您可能想尝试一下。

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