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

algorithm data-structures computational-geometry
qutron picture qutron · Dec 3, 2010 · Viewed 50.2k times · Source

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

dkamins picture dkamins · Dec 3, 2010

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.

Related questions

Initializing Half-edge data structure from vertices

I'm working on implementing various subdivision algorithms (such as catmull-clark); to do this efficiently requires a good way to store information about a grid of tesselated polygons. I implemented the half-edge data structure as outlined by flipcode, but now I'm …

Read More
FInd overlapping appointments in O(n) time?

I was recently asked this question in an interview. Even though I was able to come up the O(n²) solution, the interviewer was obsessed with an O(n) solution. I also checked few other solutions of O(n logn) …

Read More
How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More