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."

Explanation / Answer

Answer: Find the median of y.

Suppose n is odd, if we move the main pipeline slightly, then the total distance will be increased by ((n+1)/2)*d for one side and decreased by ((n-1)/2)*d for the other side, thus the total distance is increased by d. Since the optimum distance has to minimize the d, it has to be the median.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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