Fly Cheaply: On the Minimum Fuel Consumption Problem
Fly Cheaply: On the Minimum Fuel Consumption Problem
复制标题
廉价飞行：关于最低燃油消耗问题
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Efrat
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;A. Efrat
在计划航班时，有时需要在中间机场停靠，以最大程度地减少燃油消耗，即使我们有直接飞行的问题。功能L：R2×R2？R+代表任何对源机场之间的直接飞行的成本，最便宜的路径图是R2的一个细分，其中两个点位于同一区域同样的中间机场。 - 行为成本函数l：我们的一般算法在O（n4/3+？）时间中运行，更简单，更实用的变体在O（n3/2+？）时间中运行，而特殊的成本函数只需要一个特殊的成本功能o（nlogn）时间。
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 R2 and a function l: R2×R2?R+ representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of R2 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(nlogn) time.