Distance between pairs of points in a cartesian plane

Question

I was recently asked the following question, in a Foursquare interview. I was not able to code this.

We are given N points (xi,yi) where 1<=i<=N, and two numbers a and b,such that distance between two points (x1,y1) and (x2,y2) is max(a*|x1-x2|,b*|y1-y2|), how can we calculate sum of distances between each pair of points?

The number of points N is a high number.

Can anyone help with how to solve this question? Please explain the algorithm, other than the brute force one of traversing on all pairs of points.

Answer 1

Start by rescaling the axis, to get rid of a and b factors. Define x' = a * x, y' = b * y'. Then the distance is:

max(a*|x1-x2|,b*|y1-y2|) =
max(|a*x1-a*x2|,|b*y1-b*y2|) =
max(|x'1-x'2|,|y'1-y'2|)

Secondly, rotate the coordinate system by 45 degrees, to change it to Taxicab geometry. Define s = (x' + y')/2, t = (x' - y')/2. Then we have x' = s + t, y' = s - t.

Then we can rewrite definition of the distance again:

max(|x'1-x'2|,|y'1-y'2|) =
max(|s1 + t1 - s2 - t2|,|s1 - t1 - s2 + t2|) =
max(|(s1 - s2) + (t1 - t2)|,|(s1 - s2) - (t1 - t2)|) =
|s1 - s2| + |t1 - t2|
-- last equation comes from the fact that max(|a + b|, |a - b|) = |a| + |b|

With this definition we can separately sum distances along s axis and separately along t axis and add the results.

Solving one-dimensional version of this problem is quite simple. You sort the points along the axis. Then each segment between (0-based) i-th and i+1-th point will contribute (i + 1) * (N - i - 1) * distance. It's enough to sum these values.

Overall solution takes O(n lg n), since it need to sort points two times.

Answer 2

We want to compute

sum_i sum_j max(a |xi - xj|, b |yi - yj|).

Simplify the problem by mapping xi' = a xi and yi' = b yi and computing

sum_i sum_j max(|xi' - xj'|, |yi' - yj'|).

Simplify the problem by mapping ui = (xi + yi)/2 and vi = (xi - yi)/2 and computing

sum_i sum_j (|ui - uj| + |vi - vj|)
    = sum_i sum_j |ui - uj| + sum_i sum_j |vi - vj|.

To solve the first subproblem in time O(n log n), here's some Python.

def one_d(us):
    us = sorted(us)
    return sum((2 * i - (len(us) - 1)) * u for (i, u) in enumerate(us))