What is the fastest way to find the closest point to a given point?

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.

You may organize your points in an Octree. Then you only need to search a small subset.

A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.

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.

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