title: Efficient nearest neighbour search in Scala
body: <p>Let this coordinates class with the Euclidean distance,</p>
  
  <pre><code>case class coord(x: Double, y: Double) {
    def dist(c: coord) = Math.sqrt( Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2) ) 
  }
  </code></pre>
  
  <p>and let a grid of coordinates, for instance</p>
  
  <pre><code>val grid = (1 to 25).map {_ =&gt; coord(Math.random*5, Math.random*5) }
  </code></pre>
  
  <p>Then for any given coordinate</p>
  
  <pre><code>val x = coord(Math.random*5, Math.random*5) 
  </code></pre>
  
  <p>the nearest points to <code>x</code> are</p>
  
  <pre><code>val nearest = grid.sortWith( (p,q) =&gt; p.dist(x) &lt; q.dist(x) )
  </code></pre>
  
  <p>so the first three closest are <code>nearest.take(3)</code>.</p>
  
  <p>Is there a way to make these calculations more time efficient especially for the case of a grid with one million points ?</p>