Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

Question

Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can be reduced if it causes a very significant increase in performance). These vertices are currently stored as floats from 0-255, but this range can also be changed if need be, assuming it will not reduce accuracy too drastically. Also, I can store these objects in any data structure that would be beneficial for this algorithm.

I am given another such object, also with the same number (8) 3-D vertices, but of which in general it must be assumed that none of the vertices are common with any vertices included in the list of stored previous objects.

With all of this in mind, I need an algorithm that will return an object from that list that is optimally close to the test case object (close being defined in the normal, euclidean distance, sense). By optimally close, I mean that it does not have to be the global optimum if this will greatly increase performance, although if there is a quick algorithm that will always return the global optimum i would love to hear it.

Answer 1

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants. Then:

1. Define a distance function that gives the closest BB to the BB of your search-object.
2. Find the BB in the index that is closest to the BB of you search object.
3. Calculate the actual distance $d$ between the search-object and the object from the index.
4. Search the index again, this time with a window query that is by $d$ larger than the previous search BB. This should return all objects that are potentially closer than $d$.
5. Brute force all returned objects to calculate their actual distance to your search object.

Worst case complexity of the worst case is $O(N)$ for $N$ objects, but average case should be closer to $O(log N)$.

Answer 2

The best I can come up with is to compute the centroid of each object and store the centroids in a nearest-neighbor data structure; to find the matches for a test object $T$, look up its centroid in the data structure and iterate through the objects in order of the distance between their centroid and $T$'s centroid and compute the distance to each. The heuristic is to stop iteration after exploring some fraction of the objects.

Depending on how you compute the distance between two objects, this might perform arbitrarily badly in the worst case, but it's possible it might be acceptable for some workloads if you don't encounter the worst case.