title: minimal graph on spatial points
body: <p>I have a set of 3 dimensional points. I want a quick query of the k nearest neighbours of any of these points. I know that a usual way of doing this is oct-tree, however I think that with the below described data structure the query would be much faster.</p>
  
  <hr>
  
  <p>I want a minimal graph on the points as vertices, which have the following property:</p>
  
  <p>Between any 2 points P1, P2: there is a path in which for all interior point P3: </p>
  
  <p>distance(P1, P3) &lt;= distance(P1, P2).</p>
  
  <hr>
  
  <p>My problem though is that I cannot figure out how to compute this minimal graph in an affordable time.</p>