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), as shown in Figure 9.2. 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.
In order to find optimal placement we only need to find medians of y-coordinates. Claim:
The optimal y-cordinate is as follows:
a) If n is even then the optimal placement of the pipeline is either on the oil well whose y-coordinate is lower median or on oil well whose y-coordinate is upper median or anywhere between them.
b) If n odd then the optimal placement of pipeline is on the oil well whose y-coordinate is the median.
Proof:
We examine various cases in each we start out with the pipeline at a particular y-coordinate and see what happens when we move it. We denote s as the sum of north and south spurs and s' denotes the sum after we move the pipeline.
If n is even and we start the pipeline on or somewhere between oil wells whose y-coordinate are the lower median and upper median. if we move the pipeline by a vertical distance d with out crossing either of the the median wells, then n/2 of the oil wells will be d distance farther from the pipeline and n/2 of the oil wells will nearer to the pipeline. If we caculate the distance s' = s+nd/2 - nd/2 then s' = s. thus all the locations on or between the two medians is good.
Now suppose if the pipeline goes through the upper median oil well and if we increase the y-coordinate of the pipeline d- distance away(upwards) from upper median. Then there are n/2+1 oil wells farther from pipeline and n/2-1 oil wells nearer to oil well. If we calculate the distance $$s' \geq s+(n/2+1)d-(n/2-1)d $$ $$s' \geq s+2d$$ clearly s' is greater than s.we conclude that if we move the pipeline away from the upper median then it increases the total spur length. similarly if we move the pipeline away below lower median the spur length increases.
when n is even the optimal placement of pipeline is on or somewhere between oil wells whose y-coordinates are upper and lower medians.
Now lets consider n is odd if we start the pipeline at oil well whose y-coordinate is the median and move the pipeline y-coordinate by d distance. Then there are n+1/2 oil well farther from the pipeline and n-1/2 oil wells nearer to the pipeline. if we calculate the distance $$s' \geq s+ (n+1/2)d -(n-1/2)d $$ $$s' \geq s+ d $$ which greater than s. A symmetrical argument shows that moving the y-cordinate of pipeline below the median also increases the spur length. If n is odd then the optimal placement for the pipeline is the median. We use the linear-time-median algorithm.