title: Find nearest edge in graph
body: <p>I want to find the nearest edge in a graph. Consider the following example:
  <img src="https://i.stack.imgur.com/kKMp4.png" alt="yellow: vertices, black: edges, blue: query-point"></p>
  
  <p><strong>Figure 1:</strong> <em>yellow:</em> vertices, <em>black:</em> edges, <em>blue:</em> query-point</p>
  
  <p><strong>General Information:</strong>
  The graph contains about <em>10million vertices</em> and about <em>15million edges</em>. Every vertex has coordinates. Edges are defined by the two adjacent vertices.</p>
  
  <p><strong>Simplest solution:</strong>
  I could simply calculate the distance from the query-point to every other edge in the graph, but that would be horribly slow.</p>
  
  <p><strong>Idea and difficulties:</strong>
  My idea was to use some spatial index to accelerate the query. I already implemented a kd-tree to find the nearest vertex. But as Figure 1 shows the edges incident to the nearest vertex are not necessarily the nearest to the query-point. I would get the edge <em>3-4</em> instead of the nearer edge <em>7-8</em>.</p>
  
  <p><strong>Question:</strong>
  Is there an algorithm to find the nearest edge in a graph?</p>