CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
mTesseracted
mTesseracted

Reputation: 290

Efficient algorithm for generating graph edges

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; loops are not considered. A naive approach would simply loop on all possible pairs, requiring N(N-1)/2 distance calculations. Is there an existing algorithm for finding all possible edges with scaling complexity less than O(N^2)?

Upvotes: 2

Views: 190

Answers (1)

ravenspoint
ravenspoint

Reputation: 20606

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

Yes. Insert the vertex locations into a octree, then for each vertex search for vertices closer than d.

For the equivalent problem in 2D you can use a quadtree.

You can find C++ quadtree code at https://github.com/JamesBremner/quadtree

Example Usage:

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

Note that if the exact Euclidean distance is important, then post-processing is required to remove any points in the red regions.

enter image description here

For more details, check out the German tv mini-series 'Billion Dollar Code' available on Netflix.

Upvotes: 4

Related Questions