Find best circular permutation that minimizes average distance between 2 ordered lists of points

user_11841983 0
Viewed 184

Given 2 ordered sets of n points each, A and B, how do I find the best circular permutation which minimizes the average pairwise-distance (using the distance of your choice) between points.

In other words, how do I algorithmically find k such that it minimizes sum(||A[i] - B[(i + k) % n||) with 0 <= k < n? (I have omitted the division by n because minimizing the total distance should yield the same result as the mean I believe).

One extra requirement is that the algorithm should be usable in N-Dimensional spaces so I can't just sort the arrays.

I could obviously compute every pairwise distance but that would yield O(n^2) (n x n pairwise distance computation + n accumulations) complexity which is sub-optimal ([edit] I mean here that I sure hope one can do better than brute force).

Application: One application is in graphics where I want to map each point of a shape to a point of another shape without creating crossing edges. See drawing below where we map each point of the red shape to a point on the blue shape. shape_points_mapping

optimization algorithm
1 Answers

I have two ideas.

If you're willing to optimize the sum of squares of distances, then there's an O(n log n) time algorithm based on fast convolution. The modified objective allows us to find the contribution of each coordinate separately for each possible rotation. Then we sum element-wise and choose the best.

To solve the reduced problem in 1D: we want

sum_i (A[i] - B[(i+k) mod n])**2

for each k. Do some algebra:

sum_i (A[i] - B[(i+k) mod n])**2 =
sum_i (A[i]**2 - 2*A[i]*B[(i+k) mod n] + B[(i+k) mod n]**2) =
sum_i A[i]**2 + sum_i B[i]**2 - 2*sum_i (A[i]*B[(i+k) mod n]).

The first two terms are the same for all k, so just compute them. The vector of third terms for all k can be computed quickly in bulk as a constant times A convolved with the reverse of B.

My second idea is a recursive heuristic. If n is small, just brute force it. Otherwise, make a smaller instance by computing the midpoint of each pair of consecutive points in each list. Recursively align these. Then multiply the heuristic rotation by two and check it against the rotations one up and one down from it. In constant dimensions, this yields a recurrence like T(n) = T(n/2) + O(n), which is O(n).

user_21446690
Related