title: NetworkX Random Geometric Graph Implementation using K-D Trees
body: <p>So it is clear with NetworkX that they use an algorithm in n^2 time to generate a random geometric graph.  They say there is a faster algorithm possible with the use of K-D Trees.  My question is how would one go about attempting to implement the K-D Tree version of this algorithm?  I am not familiar with this data structure, nor would I call myself a python expert. Just trying to figure this out. All help is appreciated, thanks!</p>
  
  <pre><code>    def random_geometric_graph(n, radius, dim=2, pos=None):
          G=nx.Graph()
          G.name="Random Geometric Graph"
          G.add_nodes_from(range(n)) 
          if pos is None:
              # random positions
              for n in G:
                  G.node[n]['pos']=[random.random() for i in range(0,dim)]
          else:
              nx.set_node_attributes(G,'pos',pos)
          # connect nodes within "radius" of each other
          # n^2 algorithm, could use a k-d tree implementation
          nodes = G.nodes(data=True)
          while nodes:
              u,du = nodes.pop()
              pu = du['pos']
              for v,dv in nodes:
                  pv = dv['pos']
                  d = sum(((a-b)**2 for a,b in zip(pu,pv)))
                  if d &lt;= radius**2:
                      G.add_edge(u,v)
      return G
  </code></pre>