Maximum average distance between two numbers across multiple arrays

Question

Let's say you have k arrays of size N, each containing unique values from 1 to N.

How would you find the two numbers that are on average the furthest away from each other?

For example, given the arrays:

[1,4,2,3]
[4,2,3,1]
[2,3,4,1]

Then the answer would be item 1 and 2, because they are of distance 2 apart in the first two arrays, and 3 numbers apart in the last one.

I am aware of an O(kN^2) solution (by measuring the distance between each pair of numbers for each of the k arrays), but is there a better solution?

I want to implement such an algorithm in C++, but any description of a solution would be helpful.

Answer 1

After a linear-time transformation indexing the numbers, this problem boils down to computing the diameter of a set of points with respect to L1 distance. Unfortunately this problem is subject to the curse of dimensionality.

Given

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

we compute

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

and then the L1 distance between 1 and 2 is |1-3| + |4-2| + |4-1| = 8, which is their average distance (in problem terms) times k = 3.

That being said, you can apply an approximate nearest neighbor algorithm using the input above as the database and the image of each point in the database under N+1-v as a query.