I have about 1,000,000,000 points, which are the longitudes and latitudes of some places in a city, formatted like this: $(106.1231233,41.43234234)$. I also have about 20,000 points which are the longitudes and latitudes of some special places in this city. For every item in the 1,000,000,000 point data set, I have to compute which point in the 20,000 point data set is the nearest. If I were to compute on a brute-force, one by one basis, it might not complete during my lifetime. Is there an algorithm which can make this job less time-consuming? Can anyone help me?

  • 4
    $\begingroup$ You may be able to approach this using Nearest. $\endgroup$
    – DavidC
    Oct 25, 2013 at 9:34
  • 5
    $\begingroup$ Just to clarify - is this about math/algorithms in general or specifically about the software Mathematica ? $\endgroup$
    – Yves Klett
    Oct 25, 2013 at 9:42
  • 1
    $\begingroup$ If this is about Mathematica then the answer is Nearest. If it is about algorithms and data structures, then I'd say it's off topic here and there are answers on StackOverflow here. $\endgroup$
    – Szabolcs
    Oct 25, 2013 at 16:26
  • 1
    $\begingroup$ To repeat what others have stated, you'll want to use Nearest[<reference set>]. Depending on specifics of locations, you may need to make adjustments to account for the fact that (long,lat) is not a Euclidean grid and moreover there is a singularity (crossover) for longitude. $\endgroup$ Oct 25, 2013 at 16:42

1 Answer 1



After reading about geodetic conversions, I decided to do a major rewrite. Earlier versions can be found by clicking on the "edited…" link. No claims are made about speed.

My intuitions about Geodesy are rudimentary, so I relied on ideas encountered at Latitude and Stack Exchange. I also

benefited from advice given by @Rahul Narain. Kuba also pointed me to an efficiency shortcut that Belisarius had recently used.

(*Generate a random longitude in decimal degrees *)

(*Generate a random latitude in decimal degrees *)

(*radius of earth in km *)

(* 15 city points and 5 landmarks in Cartesian (XYZ) format *)
citypoints={r Cos[#2 Degree] Cos[# Degree],r  Cos[#2 Degree]Sin[# Degree],r Sin[#2 Degree]}&@@@Array[{rx,ry}&,15];
landmarks={r Cos[#2 Degree] Cos[# Degree],r  Cos[#2 Degree]Sin[# Degree],r Sin[#2 Degree]}&@@@Array[{rx,ry}&,5];

(* precomputed function for landmarks, to be used in Nearest *)

(* each city point and its closest landmark *)
Grid[Prepend[{#,Nearest[landmarks,#][[1]]}&/@citypoints,{"city point","landmark"}],Dividers-> All]


Plot the city points and landmarks. The origin is the center of the earth. x, y, z given in km. The picture in the right pane shows that the points appear to lie on a plane. Of course, we know they lie on a sphere (or ellipsoid), but the curvature of the earth is imperceptible at this scale and point of view. (Remember: all the points lie in a single city.)

(* city points in red, landmarks in blue.  Lines connect each city point to the closest  
landmark *)
Graphics3D[{Red,PointSize[.03], Point@citypoints,Blue,Point@landmarks,
Black,Line[{#,Nearest[landmarks,#][[1]]}&/@citypoints]},AxesLabel->{"x","y","z"},BoxRatios->{1,-1,-1},Axes-> True,ViewPoint->{2,.5,.5}]

enter image description here

  • 1
    $\begingroup$ It will definitelly be faster if you precalculate NearestFunction: near = Nearest[landmarks]; ({#, near[#]} & /@ citypoints). Belisarius showed this lately $\endgroup$
    – Kuba
    Oct 25, 2013 at 9:49
  • 2
    $\begingroup$ You'll have to use Nearest with GeoDistance as the distance metric, not Euclidean. This will slow things down tremendously! $\endgroup$
    – rm -rf
    Oct 25, 2013 at 10:44
  • $\begingroup$ Presuming the long/lat, minutes, and seconds are converted to a single decimal, why won't euclidean work? Besides, isn't this a one-off computation? $\endgroup$
    – DavidC
    Oct 25, 2013 at 11:34
  • 1
    $\begingroup$ @DavidCarraher Because 1 minute E from (0,0) is not the same distance as 1 minute N from (0,0). This difference only gets worse the closer you get to the poles. GeoDistance will tell you that, whereas EuclideanDistance will consider them both equally distant. $\endgroup$
    – rm -rf
    Oct 25, 2013 at 15:37
  • 1
    $\begingroup$ Since the points represent "some places in a city" and so are likely to be quite close together relative to the size of the Earth, it might be enough to scale the longitudes by $\cos\phi_m$, where $\phi_m$ is the mean latitude, and then continue to use Euclidean distances, no? en.wikipedia.org/wiki/… $\endgroup$
    – user484
    Oct 25, 2013 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.