What's an efficient way of calculating the nearest point?

Question

I have objects with location data stored in Core Data, I would like to be able to fetch and display just the nearest point to the current location. I'm aware there are formulas which will calculate the distance from current lat/long to a stored lat/long, but I'm curious about the best way to perform this for a set of 1000+ points stored in Core Data. I know I could just return the points from Core Data to an array and then loop through that looking for the min value for distance between the points but I'd imagine there's a more efficient method, possibly leveraging Core Data in some way.

Any insight would be appreciated.

EDIT: I don't know how I missed this on my initial search but this SO question suggests just iterating through an array of Core Data objects but limiting the array size with a bounding box based on the current location. Is this the best I can do?

Answer 1

I don't know that much about Core Data, but there are well known algorithms like Quadtree for solving this problem

Answer 2

I think this can help you.

Answer 3

What you're making is called Nearest neighbor search and has a wikipedia entry describing the methods use to calculate it. I think is a good start as complexities for each method are state so you can measure complexity against how how the implementation will be :)

The simplest solution to the NNS problem is to compute the distance from the query point to every other point in the database, keeping track of the "best so far". This algorithm, sometimes referred to as the naive approach, has a running time of O(Nd)

Locality sensitive hashing (LSH) is a technique for grouping points in space into 'buckets' based on some distance metric operating on the points. Points that are close to each other under the chosen metric are mapped to the same bucket with high probability

Answer 4

From what I can gather, it looks as though the best approach in this case is to return an array of points using a bounding box around the current location.

You can retrieve points within a certain range of the current location, if the returned array is empty, then increase the size of the box. Once some results come back, calculate the nearest in the array and use that point.