title: Algorithmic solution to find closest city based on lat/lon
body: <p><em>Note there are other similar questions but 1) I don't want to rely on an online service, 2) I'm looking for a clean algorithmic solution.</em></p>
  
  <p>I have a database of cities and their latitudes/longitudes. I'm looking for a way that, given an arbitrary lat/lon, finds the closest city.</p>
  
  <p>Solutions I can think of so far:</p>
  
  <ol>
  <li><p>The obvious brute force solution is, of course, to calculate all the possible distances using the <a href="http://en.wikipedia.org/wiki/Great-circle_distance" rel="noreferrer">great-circle distance</a> formula. This also takes a long time and is O(n).</p></li>
  <li><p>A modification of the <a href="http://en.wikipedia.org/wiki/Kd-tree" rel="noreferrer">KD-Tree</a> algorithm may work, but I'm at a loss as to how to modify this algorithm to work in non-cartesian coordinates, as is the case for lat/lon. We can assume <a href="http://en.wikipedia.org/wiki/Mercator_projection" rel="noreferrer">Mercator projection</a> if this helps.</p></li>
  <li><p>Use a geo-database such as PostgreSQL. This doesn't work for me, period.</p></li>
  </ol>
  
  <p>Any insights?</p>