556 views
3 votes
3 votes

Let $P_1(x, y_1),\: P_2(x, y_2), \dots, P_n(x, y_n)$ be a collection of $n$ distinct points lying on a vertical line $L$. The value of $x$ is stored in a variable, and $y_1, y_2, \dots, y_n$ are stored in an array in decreasing order. Additionally, you are given two points $S(x′, y′)$ and $D(x′′, y′′)$, one on either side of $L$. A route $R$ from $S$ to $D$ is a two-hop path $S \rightarrow P_k \rightarrow D$, where $P_k$ is one of the points from $\{P1, P2, \dots, P_n\}$. The cost of $R$ is defined as the sum of the lengths of $SP_k$ and $P_kD$. Design an $O(\log  n)$-time algorithm to find the minimum-cost route from $S$ to $D$, i.e., your task is to select an appropriate point $P_k$ on $L$ such that the cost of the route $R$ from $S$ to $D$ through $P_k$ is minimized.

2 Answers

0 votes
0 votes
I think we can apply binary search algorithm on line l for choosing an appropriate point pk first choose k =(1+n)/2; calculate distance of sp1 and sp2 if distance of sp1 is less than distance of spk then h=k-1and call caldistance(s,1, h) else l = k+1 caldistance(s, l, n) do this until k comes out to be 1 choose appropriate pk and calculate spk +pkd
0 votes
0 votes
Here we are asked to find the appropriate optimal point $P_k$ from which the distance between S to D is least. Thus the point would be where the distance between S and the point is somewhere close to the distance between the point and D.
Let y` be y1 and y`` be y2 and the array sorted in decreasing order be Y.
Using the below method we get the optimal point.

getMinPointOnLine(int[] Y, int y1, int y2):

int low = 0, high = Y.length – 1, mid = 0;

while( low <= high ) {

      mid = low + (high – low) / 2;

      int diff_y1 = Math.abs(y[mid] – y1);

      int diff_y2 = Math.abs(y[mid] – y2);

      if(diff_y1 == diff_y2) return mid;

      else if(diff_y1 < diff_y2) low = mid + 1;

       else high = mid – 1;

}

return mid;

 

To decrease the overall cost we will modify low and high params so be on the side whose height difference is greater with current point so that on the next iteration our overall cost gets reduced.

Related questions

4 votes
4 votes
3 answers
4