Maximum average distance between two numbers across multiple arrays
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.