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 - 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