Example, if i have certain geographic points in an array A=[a,b,c,d...n] and have 10 points distributed in the solution space B= [1,2,3...10], how can I allocate each member of A to the nearest point in B in the quickest way.

  • 1
    $\begingroup$ Welcome to the site! Programming questions are off-topic, here. We're happy to help with algorithms but implementing something in a specific language isn't something we do, here. $\endgroup$ – David Richerby Sep 15 '16 at 15:51
  • 1
    $\begingroup$ Are the values in A numeric, or characters as you have typed? How can you define what the "nearest point" is in this situation? $\endgroup$ – Jaken Herman Sep 15 '16 at 19:32
  • $\begingroup$ What do you mean by "geographic points:? by "solution space"? What have you tried? What approaches have you considered, and why did you reject them? $\endgroup$ – D.W. Sep 16 '16 at 1:33
  • $\begingroup$ @David this can be in any language. @ Jaken the values in A are geographic coordinates for example (120.2, 130.5) representing x and y respectively. The same case goes for the values in B. By nearest point, I meant for the values in A which pint is closest in terms of Euclidean distance $\endgroup$ – David Sep 16 '16 at 8:36
  • 2
    $\begingroup$ @David please edit your question to contain all necessary information. People are not expected to read the comments to understand your question. $\endgroup$ – adrianN Sep 16 '16 at 12:37

This looks very much like the Nearest neighbor problem. The asymptotically most efficient approach is probably computing a k-d-tree on the points in B. Constructing the tree takes $O(|B| \log |B|)$ and lookup is logarithmic, so an additional $O(|A| \log |A|)$ to find all nearest neighbours.

Please not that the constant factors for the naive approach where you just compute the distance to each point in B and take the minimum are really good. CPUs are very good at just summing squared differences. In practice it will be hard to beat that unless B is really huge.

| cite | improve this answer | |
  • $\begingroup$ A note that the quoted running time is valid in 2 dimensions, but in higher dimensions this is not valid. $\endgroup$ – D.W. Sep 16 '16 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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