What is the fastest way to find the closest point

Question

What is the fastest way to find closest point to the given point in data array?

For example, suppose I have an array A of 3D points (with coordinates x, y and z, as usual) and point (x_p, y_p, z_p). How do I find the closest point in A to (x_p, y_p, z_p)?

As far as I know, slowest way to do it is to use linear search. Are there any better solutions?

Addition of any an auxiliary data structure is possible.

Answer 1

Unless they are not organized in a proper data structure, the only way will be linear search.

Answer 2

I suggest KD-tree will work fine. Also good for nearest neighbour searches.

Answer 3

If you're doing a once-off nearest neighbour query, then a linear search is really the best you can get. This is of course assuming the data isn't pre-structured.

However, if you're going to be doing lots of queries there are a few space-partitioning data structures.These take some preprocessing to form the structure, but then can answer nearest neighbour queries very fast.

Since you're dealing with 3D space, I recommend looking at either octrees or kd-trees. Kd-trees are more generic (they work for arbitrary dimensions) and can be made more efficient than octrees if you implement a suitable balancing algorithm (e.g. median works well), but octrees are easier to implement.

ANN is a great library using these data structures, but also allowing for approximate nearest neighbor queries which are significantly faster but have a small error as they're just approximations. If you can't take any error, then set the error bound to 0.