Fly cheaply: On the minimum fuel-consumption problem

Alon Efrat, Sariel Har-Peled

Research output: Contribution to conferencePaperpeer-review


The problem of planning the cheapest flight path, given s, t, and a set of intermediate airports at which it can make a stop is presented. This problem can be formalize by letting P be a set of n points in the plane, containing two given special points s and t. To solve the cheapest path problem in the setting, the Delaunay triangulation D(P) of P, in time O(n log n) is computed, and the shortest path problem on the graph D(P) under the cost function l(.,.) is solved using the standard Dijkstra's algorithm. Since the size of D is O(n) this implies that the overall running time of the algorithm is O(n log n).

Original languageEnglish (US)
Number of pages3
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA
Duration: Jun 7 1998Jun 10 1998


OtherProceedings of the 1998 14th Annual Symposium on Computational Geometry
CityMinneapolis, MN, USA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Fly cheaply: On the minimum fuel-consumption problem'. Together they form a unique fingerprint.

Cite this