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

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

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

Answer 2

As here we have  $P1,P2,.,……,Pn$  points in the $X-Y$ $plane$  and among them no three are collinear .

and for the steepest slope as we know  $slope=tanӨ= (y2-y1)/(x2-x1)$   

so the for the steepest slope $(i.e$   $90°)$ because for the other slopes (whether it be greater than 90° or not will not be the steepest) .

now lets , maintain an array for all the points that we have in the $X-Y$ plane .in sorted order $[Ө(nlogn) ]$

P1

P2

P3

P4.

P5

P6

.    .

…………………………..

Pn

now lets ,

fix one point $(start$ $with$ $P1)$

selecting $P1$ will take constant time now in the array from ($P2$ $to$ $Pn$) perform $binary$ $search$ and for every point that we will get we have to calculate the slope between that point and $P1$ so this process will take ( $Ө(logn) + c$)  constant time for just performing the computations for the slope.

similarly do it for all the points till $Pn$ (in the worst case).

so for selecting $constant$ $time$ is required and we are selecting all the points and performing binary search on rest of the points in the array.

so TC will be 

$TC = Ө(1)*Ө(n)$ [for selecting all points once]  *  $Ө(logn)$[for binary search everytime]  + $Ө(nlogn)$ [for sorting the array]

so,   $TC$  =  $Ө(nlogn)$ + $Ө(nlogn)$  = $Ө(nlogn)$

$OPTION$ $B$ $IS$ $CORRECT!$

Comments

yes but can you explain why we are sorting the points into an array ..? is it really necessary?