Dark Mode

4,437 views

35 votes

Let $P_1, P_2,\dots , P_n $be $n$ points in the $xy$-plane such that no three of them are collinear. For every pair of points $P_i$ and $P_j$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ be the line with the steepest gradient among all $n(n -1)/2$ lines.

The time complexity of the best algorithm for finding $P_a$ and $P_b$ is

- $\Theta\left(n\right)$
- $\Theta\left(n\log n\right)$
- $\Theta\left(n\log^2 n\right)$
- $\Theta\left(n^2\right)$

Reference ->

https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

On above link take a look on Mcdowella's explanation.

8

45 votes

Best answer

Answer: **B**

Gradient $= y_2 - y_1 / x_2 - x_1$

For gradient to be maximum $x_2 - x_1$_{ }should be minimum. So, sort the points (in $\Theta(n\log n)$ time) according to $x$ coordinate and find the minimum difference between them (in $\Theta(n)$ time).

Best complexity: $\Theta(n\log n +n)$ which leads to B.

https://www.careercup.com/question?id=4787065684230144

https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

3

4

0

0

6

0

1

I have a basic doubt, if we want the gradient to be minimum, then we want x2-x1 as max, so instead of sorting entire array in nlogn time, why can't we take the max and min values of x which will take O(n) time, then difference between this max and min x value will always be max. Similarly we can get first 2 min elements of Y in O(n) time. What crucial part I'm missing I'm not getting

I went through the mentioned links however it didn't help to solve this query.

Thanks in advance

I went through the mentioned links however it didn't help to solve this query.

Thanks in advance

1

0

even the part 1 of this combined question tells that only adjacent points can give max. slope.so sorting the points on the basis of x axis is perfect; it takes O(nlogn).(we must keep separate array for y coordinate too and arrange it as per x, it would be later used.this wont increase time complexity as its done simultaneously)

but now, instead of taking just min. of adjacent x coordinates, we must find “slope” between adjacent points and keep a variable MAX. which can be updated as we traverse the entire array. this is mandatory because we may take 2 points whose difference in x might not be minimum amongst other pairs, still its difference in y is so big as to give a higher slope).this will still take O(n).

hence,TC=O(nlogn +n)=O(nlogn).

but now, instead of taking just min. of adjacent x coordinates, we must find “slope” between adjacent points and keep a variable MAX. which can be updated as we traverse the entire array. this is mandatory because we may take 2 points whose difference in x might not be minimum amongst other pairs, still its difference in y is so big as to give a higher slope).this will still take O(n).

hence,TC=O(nlogn +n)=O(nlogn).

2

0

0

edited
Sep 30
by Pranavpurkar

0

@Pranavpurkar no it will be O(n), if the points are sorted in ascending order acc to x- coordinate.

Just take sample example:

(1,2),(7,5),(9,6),(14,9)

So, acc to this first two minimums are 1 and 7 and after the subtraction, it will be 6.

Then you will consider between 7 and 9 and after the subtraction, it will be 2.

Then you will consider between 9 and 14 and after the subtraction, it will be 5.

For, the steepest slope the difference between the x-coordinate should be minimum and that is the line between (7,5) and (9,6).

So, to find that we have to scan the entire x-coordinate. Therefore, it will be O(n).

2

3 votes

Answer is well explained in this link:

https://www.careercup.com/question?id=4787065684230144

**option B**