1

我在二维平面（xy）中有一组点，比如 n 个点。

(x1, y1), (x2, y2), (x3, y3), ......................., (xn, yn)

我的目标是绘制图表。图中的两个节点（点）将连接 iff abs(difference in x coordinate) + abs(difference in y coordinate) = L(given)。

可以做到O(n*n)的。是否有可能有效地做到这一点。

顺便说一句，我正在尝试解决这个问题

4

5 回答 5

2

您可以在 O( n  log  n  +  E ) 时间内完成此操作，其中E是您最终得到的实际边数（即邻居对的数量）。

对于任何给定点，其允许的邻居位置形成边长L √2的菱形：

        *
      *   *
    *       *
  *           *
*       o       *
  *           *
    *       *
      *   *
        *

如果您按x  +  y对点进行排序并回退到x  -  y，然后一个 O( n  +  E ) 通过排序点将让你找到这种类型的所有邻居：

        *
          *
            *
              *
        o       *

对于每个点。（为此，您使用一个索引i来跟踪您正在为其寻找邻居的当前点，并使用一个单独的索引j来跟踪允许的邻居的行，例如x j  -  y j  =  x i  -  ; y i  +  L。这可能听起来像 O( n 2 )，因为数组中有两个索引；但诀窍是j随着 单调递增i，因此每个i和j只通过数组一次。这将甚至是 O( n ) 通行证，除非你确实找到 (x i ,  y i )，那么您需要重新将它们视为 ( x i+1 ,  y i+1 ) 的潜在邻居，因此您不能递增j。所以结果是 O( n  +  E ) 通行证。）

然后您可以按y对它们重新排序 -  x回退到x  +  y，并重复该过程以找到这些邻居：

        *
      *
    *
  *
*       o

而且由于邻居是对称关系，因此您实际上不需要担心剩余的邻居：

        o
  *           *
    *       *
      *   *
        *

（总的 O( n  log  n  +  E ) 时间包括 O( n  log  n ) 对点进行排序的时间，加上两次 O( n  +  E ) 传递的时间。）

于 2016-12-16T00:53:19.007 回答
1

考虑到数据的某些假设，当然可以有效地做到这一点。我会考虑更一般的情况。例如，如果点是均匀分布的，并且相互作用距离L(given)相对于数据的传播很小，那么可以O(n)通过对粒子进行分箱来转换问题。

这会将您从左侧的情况带到右侧的情况：

在平面上合并粒子

bin 大小取为>=L(given)，对于任何粒子，粒子的 bin 和 8 个相邻的 bin 都被搜索。如果一个 bin 中的粒子数平均为一个常数d，那么问题是可以O(9dn)=O(n)及时解决的。

于 2016-12-15T18:59:35.677 回答
0

与上述相关的另一种可能性是使用稀疏矩阵结构将1值存储在所有点的位置和0其他位置的值。

虽然为此存在很好的库，但您可以通过提出一个结合您x和y坐标的哈希来伪造它。在 C++ 中，它看起来像：

std::unordered_set< std::pair<int,int> > hashset;

预先调整散列表的大小，使其比您需要的大 30-50%，以避免昂贵的重新散列。

将所有点添加到哈希集中；这需要O(n)时间。

现在，交互距离L(given)定义了围绕中心点的菱形。您可以为这颗钻石预先生成一个偏移量列表。例如，如果L=2，则偏移量为：

int dx[]={0,-2,-1,0,1,2, 1,0,-1};
int dy[]={0, 0, 1,2,1,0,-1,2,-1};

现在，对于每个点，遍历偏移列表并将它们添加到该点的坐标。这会生成一个隐含的邻居位置列表。使用哈希集检查该邻居是否存在。如果（对从第一个节点可到达的邻居数量有一些限制），这需要O(n)时间并且是有效的。8L << N

于 2016-12-15T19:41:54.017 回答
0

我非常喜欢 ruakh@ 的解决方案。另一种方法将允许在不损失效率的情况下逐步增加点集。

要添加每个点 P，您将在树中搜索满足您条件的点 Q，并在找到任何边时添加边。

在任何 kd 树搜索的每个级别，都有每个子节点表示的矩形范围可用。在这种情况下，只有当且仅当其范围可能包含与 PIe 匹配的点时，您才会继续“向下”搜索子节点，矩形必须包含 ruakh@ 描述的菱形的某些部分。

kd 树搜索的分析通常很棘手。我很确定这个算法在随机点集的预期 O(|E| log n) 时间内运行，但也很容易想象性能更好的点集和其他更差的点集。

于 2016-12-16T02:01:28.627 回答
-1

考虑线y = x并y = -x 考虑每个点与这些线的距离。仅当两点与这两条线的距离差正确时，它们才会连接。因此，您可以按与这些线的距离对所有点进行存储。然后在每个桶中，有一个有序的点图（按它们沿线的距离排序）。此有序地图中正确距离内的任何点都应在图中连接。应该是 N*Log(N) 最坏的情况，即使所有点都在彼此之上。

于 2016-12-15T21:43:34.810 回答