title: Efficient generation of a Gabriel graph?
body: <p>A <a href="https://en.wikipedia.org/wiki/Gabriel_graph" rel="nofollow noreferrer">Gabriel Graph</a> is a set of vertices such that two vertices i and j are linked if there are no vertices in the disk of diameter (i,j).</p>
  
  <p>I want to generate Gabriel graphs with a lot of vertices. Nevertheless, for 1000 vertices, the time needed to create such a graph is quite long, and I need more than 1000 vertices.</p>
  
  <p>My idea was this one:</p>
  
  <pre><code>def dist(I,J):
      return math.sqrt( (I[0]-J[0])**2 + (I[1]-J[1])**2 )
  G=nx.empty_graph(N) #empty graph
  I=[(random.random(),random.random()) for i in range(0,N)] #nodes positions
  for i in range(0,N-1):
      for j in range(i+1,N):
          xm=0.5*(I[i][0] + I[j][0]) #M is the center of i and j
          ym=0.5*(I[i][1] + I[j][1])
          M=(xm,ym)
          d=min(dist(M,I[i]),dist(M,I[j])) #d is the half-distance between i and j
          possibilites=[k for k in range(0,N) if xm-d&lt;I[k][0]&lt;xm+d and ym-d&lt;I[k][1]&lt;ym+d] #we are only looking around the point M
          inter=[k for k in possibilites if dist(I[k],M)&lt;d]
          if len(inter)==0:
              G.add_edge(i,j)
  </code></pre>
  
  <p>Do you have a better idea to generate this graph?</p>