生成图边的有效算法

Question

给出了一组尺寸为N的三维空间坐标和最大连接距离d的顶点集合，是否有一种有效的算法来寻找距离小于d的顶点的所有无向边；不考虑环。一种简单的方法就是在所有可能的对上循环，需要N(N-1)/2距离计算.是否有一种现有的算法来寻找复杂度小于O(N^2)的所有可能的边？

Answer 1

给出了一组尺寸为N的三维空间坐标和最大连接距离d的顶点集合，给出了一种有效的算法来寻找距离小于d的顶点的所有无向边。

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

对于2D中的等价问题，可以使用四叉树。

您可以在C++上找到https://github.com/JamesBremner/quadtree四叉树代码。

示例用法：

        // 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));

请注意，如果精确的欧氏距离很重要，则需要后处理才能删除红色区域中的任何点。

​

​

欲了解更多细节，请参阅Netflix上的德国迷你电视连续剧“十亿美元密码”。