从给定的事实中有效地获取图形

Question

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

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

我的objective是画图。图中的两个节点（点）将连接 iff abs(difference in x coordinate) + abs(difference in y coordinate) = L(given).

可以做到O(n*n)。有没有可能高效地做到。

顺便说一下，我正在尝试解决 this 问题

Answer 1

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

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

bin 大小被取为>=L(given)，并且对于任何粒子，该粒子的bin 和8 个相邻的bin 都被搜索。如果 bin 中的粒子数平均为常数 d，则问题可在 O(9dn)=O(n) 时间内解决。

Answer 2

与上述相关的另一种可能性是使用稀疏矩阵结构在所有点的位置存储 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 是有效的（有一些关于从第一个节点可达的邻居数量的限制）。

Answer 3

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

Answer 4

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

对于任何给定点，其允许的相邻位置形成边长为L√2:

的菱形

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

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

每个点。（为此，您使用一个索引 i 来跟踪您正在为其寻找邻居的当前点，并使用一个单独的索引 j 来跟踪允许的邻居线，这样 x_j − y_j = x _i − y_i + L。这可能听起来像 O(n²)，因为数组中有两个索引；但诀窍在于 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(n log n + E)时间包括O( n log n)对点进行排序的时间，加上两个O(n + E) 通过。)

Answer 5

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

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

在任何 k-d 树搜索的每一层，都有可用的矩形范围由每个 child 表示。在这种情况下，当且仅当其范围可能包含与 P 匹配的点时，您才会继续搜索 "down" 到 child 节点。即，矩形必须包括 ruakh 的菱形的某些部分@描述。

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

从给定的事实中有效地获取图形

Efficiently obtain the graph from given facts

algorithm

math

undirected-graph