title: Efficient algorithm for finding closest point in a finite set to another point
body: <p>I have a list L of ~30k locations (written as longitude/latitude pairs), and a list E of ~1m events (with locations written as longitude/latitude pairs), each of which occurs at a point in L. I want to tag each event in E with its corresponding location in L. But the cooordinates in L and E are rounded differently&mdash;E to five decimal places, L to thirteen&mdash;so ostensibly identical coordinates can actually differ by ~10^-5 degrees, or ~1 meter. (Points in L are separated by at least ~10 m.)</p>
  
  <p>I thus need the nearest point in L to every point of E; the obvious O(|L||E|) brute-force algorithm is too slow. L is small enough compared to E that algorithms that preprocess L and amortize the preprocessing time over E are fine. Is this a well-studied problem? The links that I can find are for related but distinct problems, like finding the minimal distance between a pair of points in one set.</p>
  
  <p>Possibly relevant: <a href="https://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow noreferrer">Voronoi diagrams</a>, though I can't see how preprocessing L into a Voronoi diagram would save me computational time.</p>