### Abstract

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 language | English (US) |
---|---|

Pages | 143-145 |

Number of pages | 3 |

State | Published - Jan 1 1998 |

Externally published | Yes |

Event | Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998 |

### Other

Other | Proceedings of the 1998 14th Annual Symposium on Computational Geometry |
---|---|

City | Minneapolis, MN, USA |

Period | 6/7/98 → 6/10/98 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

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

## Cite this

Efrat, A., & Har-Peled, S. (1998).

*Fly cheaply: On the minimum fuel-consumption problem*. 143-145. Paper presented at Proceedings of the 1998 14th Annual Symposium on Computational Geometry, Minneapolis, MN, USA, .