Assume that we are given the coordinates of n airports. Given an airplane that can fly a distance of b miles without refueling, a typical query is to determine the smallest value of t such that the airplane can travel between any pair of airports using flight segments of length at most b miles, such that the sum of the lengths of the flight segments is not longer than t times the direct “as-the-crow-flies” distance between the airports. This problem falls under the general category of bottleneck problems. In our case, the stretch factor, i.e., the value of t, is a measure of the maximum increase in fuel costs caused by choosing a path other than the direct path between any source and any destination. (Clearly, this direct path cannot be taken if its length is larger than b miles.)
展开▼
