This question is from Introduction to Algorithms, #9.3-9: \"Professor Olay is co

Question

This question is from Introduction to Algorithms, #9.3-9:

"Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route (either north or south). Given the x- and y- coordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal location in linear time."

The solution from the solutions manual to this question is available online and I have looked over it multiple times. However, I do not understand it very well. Can someone please explain it in a different way?

Explanation / Answer

It's simple.... visualize a co-ordinate plane, where the main pipeline is parallel to the x-axis.. say the y co-ordinate of ith point is yi (assume yi's to be sorted)... thus if the main pipeline is separated from the x-axis by y points, then distance of all pipelines from that line is yi-y. Thus the total length of the pipe is sigma(from 0-n) |y - yi| .

Our aim is to find out y such that this sum is minimised...

Say if i points are above the line and j points are below. If i>j then if we increase y to y + dy then definately the sum will decrease by (i-j)dy

and if i<j then if we decrease y to y - dy then also the sum will decrease by (j-i)dy

Thus the optimal solution is if there are equal number of points above and below the main line..

Thus if n is odd the the line passes through the centre point.

and if n is odd then main line can be anywhere between the two centre points...

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.