# How to find the number of pair of points that can form a line with positive slope fast?

Given n pairs of points, how can we get the number of pair of points that can form a line with positive slope fast?

Then there are n lines, where the i-th line contains two integers xi and yi specifying the x and y-coordinates of i-th point. No two points have the same x-coordinate and no two points have the same y-coordinate.

My idea is to sort x first and then compare each point with the other below it. But it is still O(n^2)

-
What are your thoughts? What do you already know? –  Felix Kling Apr 28 '12 at 14:54
Are points paired? –  MBo Apr 28 '12 at 15:05
If there are n lines, then it takes O(n) time to get lines with positive slopes –  MBo Apr 28 '12 at 15:19
I don't think it is possible in O(n)... –  Bear Apr 28 '12 at 15:23
add comment

## 2 Answers

Sort descending by x and then count the number of inversions in y. Both steps are O(n log n).

Explanation: the number of (unordered) pairs with positive slope is the number of pairs {(xi, yi), (xj, yj)} such that xi > xj and yi > yj. When we sort descending by x, we make it so that xi > xj if and only if i < j. The definition of an inversion in the ys is a pair i < j such that yi > yj.

Counting the number of inversions quickly.

-
Could you mind explaining more,plx –  Bear Apr 29 '12 at 11:46
add comment

Pick a point (randomly is easiest and has a good expected running time, although you can find a median point deterministically in linear time), split the axes into four quadrants:

``````  x        |
|   x   x
x     |  x
-----------x-----------
x        |
x       |      x
| x
``````

Denote the quadrants in counter-clockwise direction from top-left by `I`,`II`,`III`,`IV`:

``````II  | I
----|----
III | IV
``````

We shall disregard points that lie on the axes (edge case with theoretical probability of 0, and easily dealt with practically).

Note that all points in quadrant `III` form a positively-sloped line with all points in `I`, similarly no points from `II` will form p.s. lines with points in `IV`, so we recursively call:

``````NumPSLines(G) = |I|*|III| +
NumPSLines(I U II) +
NumPSLines(II U III) +
NumPSLines(III U IV)
``````

Where `U` denotes union.

Assuming (proof left to reader) that the expected values `E(|I|) = ... E(|IV|) = |G|/4 = n/4` and that the partition into quadrants is linear then we get an expected run time of:

``````T(n) = O(n) + 3T(n/2)
= O(n) + ... + 3^k * t(n/2^k) // where k = log2(n)
= O( log2(n) * 3^log2(n) )
= O(n^(log2(3)) * logn)
~ O(n^1.6 * logn)
``````

Not sure if that bound is tight; haven't thought about it much.

This solution can be super optimised, although it's a start.

-
you are so clever... –  Bear Apr 29 '12 at 6:15
@Bear, thanks, although the other answer is slightly more efficient and simpler, you should probably choose it! –  davin Apr 29 '12 at 10:01
add comment
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}