Fly Cheaply: On the Minimum Fuel Consumption Problem

Timothy M. Chan, Alon Efrat

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)330-337
Number of pages8
JournalJournal of Algorithms
Issue number2
StatePublished - Nov 2001
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Fly Cheaply: On the Minimum Fuel Consumption Problem'. Together they form a unique fingerprint.

Cite this