Geek Answers Handbook

The distance between pairs of points in the Cartesian plane

Recently I was asked the following question in an interview with Foursquare. I could not code this.

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

The number of points N is a large number.

Can anyone help to resolve this issue? Please explain an algorithm different from brute force passing through all pairs of points.

+5
source share
2 answers

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

 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 45 degrees to change it to taxi geometry. Define s = (x' + y')/2, t = (x' - y')/2 . Then we have x' = s + t, y' = s - t .

Then we can rewrite the definition of 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|

Using this definition, we can separately summarize the distances along the s axis and separately along the t axis and add the results.

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

The general decision is made by O(n lg n) , since he needs to sort the points twice.

+6
source

We want to calculate

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

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

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

Simplify the problem by matching 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 subtask in O (n log n) time, here is some Python.

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

More articles:


All Articles