edited by
5,100 views
25 votes
25 votes

Let $P_{1},P_{2},\ldots,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 amongst all $\frac{n(n -1)}{2}$ lines.

Which one of the following properties should necessarily be satisfied ?

  1. $P_{a}$ and $P_{b}$ are adjacent to each other with respect to their $x$-coordinate
  2. Either $P_{a}$ or $P_{b}$ has the largest or the smallest $y$-coordinate among all the points
  3. The difference between $x$-coordinates $P_{a}$ and $P_{b}$ is minimum
  4. None of the above
edited by

8 Answers

1 votes
1 votes
Consider 2 point a,c  and line of infinite length passing through them point b can be above line ac or below as 3 point can't be collinear, let us assume that b is below line ac now we find slop ab= Delta p and bc = delta q either of them will be greater ( assume delta p> delta q)

Similary if point b would be above line then result would be exactly opposite (delta q> p)

This is only possible when  are sorted as per their x coordinate

consider 3 points  
A=(x1, y1) = (1,10)
B=(x2, y2) = (2,2)
C=(x3, y3) = (4,22)

Cleary we can never see ab= -8 bc= 10 and ac= 4 so bc it's our gradient.

Thus answer is A
edited by
0 votes
0 votes

The answer is option A

This is not exactly an easy question and and even after reading the Stack overflow  link given in the best answer it didn’t really click. After reading the SO answer plotting the figure did the trick.

Using a brute-force algorithm we can compute the slope of each line i.e each pair of  points. Since there are nC2 pairs of points the algorithm would take O(n^2) time.

We can model it into a greedy algorithm using the following argument – the points a(x1.y1) and b(x2,y2) that give the maximum slope are adjacent to each other in terms of their x coordinate, i.e their x coordinates are consecutive terms when sorted by x coordinate.

 

This is can be tested out using out figures and an idea of a convex boundary.

A picture showing that adjacent x coordinates have max slope
Adjacent points P3 and P4 have max slope
 

From the figure we can see that the maximum slope will be formed by p3 and p4 and these have adjacent x coordinates. This can be used to further restrict out sample space and our algorithm can be done in O(n) time.

 

Additionally we can also find counterexamples for all the other options.

Option B – If the x is proportionately large as the difference in the Y coordinates the slope will not increase

Option C – If the difference in x coordinates is minimum and Y coordinates change is 0 that will not be max either

The only real confusion is between Option A and D  but since we proved A 

The answer is A

0 votes
0 votes

Steepness of gradient means | ( y2-y1) / ( x2 – x1 ) |.

For option ( A ) ;

 

Option (B) tells that either y1 or y2 is the smallest or largest y coordinate in the system. But being highest gradient does not mean it follows given statement as it depends on x1,x2 coordinates also. For eg: gradient between line XY = ( 0,0 ) to ( 2,10 ) = 5 ; gradient between  line AB = ( 1,2 ) to ( 2,8 ) = 6. Here vertices of AB are neither highest y nor lowest y co ordinates. still its gradient higher than XY.

Option (C) Similar to option B, option is telling x coordinates is minimum. Again we cant deduct that from highest gradient as it does not tell anything about y coordinates. For eg: line XY = (0,0) to (1,2) have gradient = 2; line AB = ( 1,0 ) to ( 3, 10 ) have gradient  =5. Here vertices of AB have closer x coordinates. Yet that line have low gradient.

So Option (A) Correct.

Answer:

Related questions

61 votes
61 votes
8 answers
1
Ishrat Jahan asked Oct 29, 2014
16,031 views
Let $A$ be the matrix $\begin{bmatrix}3 &1 \\ 1&2\end{bmatrix}$. What is the maximum value of $x^TAx$ where the maximum is taken over all $x$ that are the unit eigenvect...
46 votes
46 votes
5 answers
4