生成图边的高效算法

Question

给定一组具有大小为 N 的 3D 空间坐标和最大连接距离 d 的顶点，是否有一种有效的算法来找到连接距离小于 d 的顶点的所有无向边；不考虑循环。一种天真的方法会简单地循环所有可能的对，需要 N(N-1)/2 距离计算。是否有现有算法可以找到缩放复杂度小于 O(N^2) 的所有可能边？

Answer 1

Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d

是的。将顶点位置插入八叉树，然后为每个顶点搜索比 d 更近的顶点。

对于二维中的等效问题，您可以使用四叉树。

您可以在 https://github.com/JamesBremner/quadtree

找到 C++ 四叉树代码

用法示例：

        // construct vector of random points
        std::vector<cPoint> vp = random(count);

        // construct quadtree of points
        cCell quadtree(cPoint(0, 0), 100);
        for (auto &p : vp)
            quadtree.insert(p);

        // quadtree search
        // returns vector of all points within 2 by 2 box around point 10,10
        auto fp = quadtree.find(cCell(cPoint(10, 10), 2));

请注意，如果精确的欧氏距离很重要，则需要进行 post 处理以移除红色区域中的所有点。

有关详细信息，请查看 Netflix 上的德国电视迷你剧集 'Billion Dollar Code'。

生成图边的高效算法

Efficient algorithm for generating graph edges

algorithm

graph-theory

graph-algorithm