Given a set of n points (x,y), is it possible to find the number of pairs of points with negative slopes between them in O(n logn) time?

Question

Given a set of n points on a 2-d plane of the form (x,y), the aim is to find the number of pairs of all points (xi,yi) and (xj, yj) such that the line joining the two points has a negative slope.

Assume that, no two xi's have the same value. Assume all points lie within [-100,100] or some other range.

Answer 1

What you are asking about is equivalent to finding the number of non-inversions in the array of the ys you will obtain when you sort the points in respect to x. You can afford this sorting - it is O(n log n).

I remind you that inversion is i > j and a[i] < a[j]. The equivalence I am speaking of is easy to prove.

Imagine you have 6 points (4, 4), (2, 1), (6, 6), (3, 3), (5, 2), (1, 5). After you sort them in respect of x you obtain: (1, 5), (2, 1), (3, 3), (4, 4), (5, 2), (6, 6). You can see that the negative slopes are formed by <(2, 1), (3, 3)>, <(2, 1), (4, 4)>, <(2, 1), (5, 2)>, <(2, 1), (6, 6)> etc. All the pairs whose ys are not in inversion.

Number of inversions can be counted in O(n log n) using augmention of the merge sort algorithm: basically you only need to increase the counter of inversions every time you choose to add value of the right subarray (the one containing larger indices). You increase the number of inversions with the amount of still not processed values from the left subarray.

Here is example of the counting the number of inversions.

Initial array 5 1 3 4 2 6  inv := 0 // Total inversions: 6
merge step 1: <5 1 3> <4 2 6> inv = 0
merge step 2: <5> <1 3> | <4> <2 6> inv = 0
merge step 3: <5> [<1> <3>] | <4> [<2> <6>] inv = 0
merge step 4: <5> <1 3> | <4> <2 6> inv = 0 // both pairs were already sorted
merge step 5: <1 3 5> | <2 4 6> inv = 3 // we add one for 1, 3 and 2
merge step 6  <1 2 3 4 5 6> inv = 6 // we add 2 (3 and 5) for 2 and 1 for 4 

After you find the number of inversions the number of non-inversions in the total number of pairs (n * (n - 1)) / 2 minus the number of inversions inv.

In the example case this is: 6 * 5 / 2 - 6 = 9.