GATE IT 2007 | Question: 81

Question

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

• A. $\Theta\left(n\right)$
• B. $\Theta\left(n\log n\right)$
• C. $\Theta\left(n\log^2 n\right)$
• D. $\Theta\left(n^2\right)$

Comments

NICE ARTICLE.

---

Reference ->

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

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

---

We need to use stable sorts like Merge sort ... Correct me if i am wrong ...

Answer 1

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

Comments

@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).

---

samarpita

YES ! got it now.

Thanks :)

---

for max slope it is correct that x2-x1 should be minimum but Instead we should look for -

difference b/w x-coordinates should be minimum && difference b/w y-coordinates should be maximum. it can be a case where a point having minimum difference in x-coordinate and diff. b/w y-coordinates is also min. but for max slope, diff. b/w y-coordinates should be max. also 

Answer 2

B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.

Comments

Y coordinates also matter in slope. (y2-y1/x2-x1)

Answer 3

I think D, for each and every pair we have to check.

Comments

To see 3 points are linear or not, we can do binary search.
then we have to find theta.

Answer 4

Answer is well explained in this link:
https://www.careercup.com/question?id=4787065684230144

option B