Fly Cheaply: On the Minimum Fuel Consumption Problem |
| |
Authors: | Timothy M. Chan Alon Efrat |
| |
Affiliation: | Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canadaf1;Computer Science Department, University of Arizona, Tucson, Arizona, 85721, , f2 |
| |
Abstract: | In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in 2 and a function l: 2 × 2 → + representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of 2 where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n4/3 + ) time, and a simpler, more practical variant runs in O(n3/2 + ) time, while a special class of cost functions requires just O(n log n) time. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|