0
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ How do you define how close two objects are? I know what is meant by the distance between two points; what definition of the distance between two objects do you use? I don't understand what is the definition of 'optimally close'; you tell us what it isn't, but not what it is. Do you want a heuristic or approximation algorithm that will give an answer that is close to the optimum? $\endgroup$
    – D.W.
    Feb 6, 2020 at 6:00
  • $\begingroup$ @D.W. I left things a bit vague to avoid painting myself into a corner so to speak and confining the problem so much that it didn't leave any wiggle room. I am very much open to any suggestions or modifications on both the distance / cost function and the overall view of the solution. My thinking, though, was that the distance function would be the minimum sum of euclidean distances, and my hope was for something along the lines of a data structure that would make sorting these distances relatively fast. $\endgroup$
    – Fred E
    Feb 6, 2020 at 13:03
  • 1
    $\begingroup$ Are objects small? If so, you could use a nearest-neighbor data structure. $\endgroup$
    – D.W.
    Feb 6, 2020 at 18:51
  • $\begingroup$ Im not sure what you mean by small. Each of the dimensions can be reduced to a range of 0-1 if that is useful, but by default they are range 0-255. If you mean the data size, they are stored as 16 bits but I think I can reduce the size here as well without too much loss. I have been looking into Rtrees, which seem to be pretty useful, but I am not sure if there is a better structure for this specific problem. Do you have any idea on this? $\endgroup$
    – Fred E
    Feb 6, 2020 at 19:01
  • $\begingroup$ Is each object small (in extent) compared to the space it is in? e.g., it has small volume, its bounding box has small volume and is small in each dimension. $\endgroup$
    – D.W.
    Feb 6, 2020 at 19:10

2 Answers 2

2
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perhaps consider objects in order of decreasing volume (too?), OP mentions some objects can be quite large. $\endgroup$
    – vonbrand
    Feb 19, 2020 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.