I need to write a program that does the following:Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal placesStore them in a data structure onceProvide a nearby lookup function that can efficiently return the N closest objects for a given lat/longCurrently, I'm doing the following, which is suboptimal:Store all objects in a hash, with array keys like [integer_latitude, integer_longitude]At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at [0,0], I can get all objects within 1 degree by pulling [-1,0], then [0,0], then [1,0], then [0,-1], etc.Order the found objects by actual distance to the target and take the top NThis is obviously inefficient, because often there are many more matches than N.One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.Is there some well-established way of doing this search efficiently?
What data structure would help find nearby coordinates quickly?
data structures;computational geometry;search algorithms;search problem