I have a set of nodes where each node $n_i$ is associated with a cartesian coordinate $\vec r_i$ and a radius $\sigma_i$. I want to generate a graph data structure where nodes $n_i$ and $n_j$ are connected by an undirected edge if $|r_{ij}| < \sigma_i + \sigma_j$. This is not my field and I am interested in efficient algorithm/workflow/software suggestions. I am working in C++.
1 Answer
This is the intersection graph of a set of spheres. The case of 2D disks, all of the same size, is well-studied; its intersection graph is known as a unit disk graph, and it has been studied in some depth in the literature. I don't know if your case has been studied in the literature, but those are some search terms you could use to try to find related work.