# Potatoes in space! - Correlating sets of unordered 4d data

(I asked this question some time back but got no answers or comments. It's a pretty big question so therefore I thought dividing it into several questions might make it easier to answer. The original thread is here: Matching sets of 3d position data)

Imagine a cube filled with air and ~5000 levitating potatoes. The distance between two potatoes is usually an order of magnitude larger than their diameter and their distribution is pretty random but not normal. The size and number of potatoes in the cube is unknown but I have two methods for measuring it: reference method A (assumed to be the truth), and method B. Both methods have given me the x-, y- and z-position of each potato that it found along with it's size.

QUESTION: The two lists of x-, y-, z- and size data are not in the same order. Is there some method that allows me to assess how well method B measures the size and position of the potatoes without having to determine which two entries in list A and B that refers to the same potato?

If I were to make a method up I might imagine that I plotted the potatoes as blue and red spheres in space (size given by size data) and checked how much of the volume was purple compared to blue or red. But I'd rather use a real method than making something up, and I figure this problem can't possibly be a new one.

• Your question seems to be not quite clear. method that allows me to assess how well method B measures the size and position of the potatoes. Of the entire cloud of the potatoes or of each individual potato? If you ask about the latter you have to find a way to identify the same potatoes in the two clouds. – ttnphns Nov 27 '14 at 19:21
• The entire cloud. Just calculating the density gives a measure of the size estimation, but that says nothing about the positioning. – mdo Dec 1 '14 at 15:57

"Assume a spherical potato" is probably a reasonable thing to do here.

As the blue part space is essentially random, you cannot represent it more efficiently than your list of 5000 spheres. What would be possible is a spatial index that allows for an efficient search, so you don't need 5000*5000 comparisons.

My gut feeling would be to sort the red potato indices in all 3 dimensions. This gives us 3 lists. Now given a blue potato, search for its X coordinate in the red-X list, it's Y coordinate in the red-Y list and its Z coordinate in the red-Z list. As these three lists are essentially projections, all 3 lists of candidates will be mostly wrong. However, there's in all likelyhood going to be only a single common candidate on all 3 lists.

Finding numbers common to N lists is efficient if you first sort the lists. (This is basically just a matter of determining the union of N lists.) Start with x = the smallest number of the first list. Do a binary search for x on the second, third list etc until you don't find x. Keep track of the points where you found x. At that point, set x to the next number from the first list. As you have kept track of the positions in all lists where you found x so far, you know you don't need to search before those points. This means the binary search ranges shrink fairly rapidly.

Note that there may be several candidates if one read potato can overlap more than one blue potato.

There's one slight challenge in the projection phase, and that's that the potatoes all have different sizes. You can solve this by using 3*2 lists, for red-min-X and red-max-X coordinates etc. This will obviously also produce 6 lists of candidates (again:indices), but the lists pairwise will have a lot of commonality. Don't merge those pairs. The union of the min-X and min-Y candidate lists is a lot smaller than the union of the min-X and max-X candidate lists.

Note that you could also add non-orthogonal projections by sorting on X+Y, X+Y-Z etc, but for the simple sphere case with plenty of distance between them this probably does not add value. The list of candidate pairs will be small enough to calculate the overlap% for all of them, and accept that some false pairs turn out to have 0% overlap.

• Correct me if I'm wrong, but this answer explains how to match up the entries in the two lists? Not how to obtain an figure of merit? – mdo Dec 1 '14 at 15:49
• Well, I had assumed that percentage overlap (last sentence) is a reasonable figure of merit. I don't know if you want to do a weighted or unweighted sum to come up with an overall number, that's up to you. But no, there's no shortcut. You "red" and "blue" subspaces have no workable mathematical structure except as the union of 5000 of spheres. – MSalters Dec 2 '14 at 12:52