Approximation algorithms for geometric shortest path problems

Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack

2000 · 74 citations · 18 references

DOIFull text

Open access

Concepts

Abstract

We consider the classical geometric problem of determining a shortest path through a weighted domain. We present approximation algorithms that compute e-short paths, i.e., paths whose costs are within a factor of 1 + e of the shortest path costs, for an arbitrary constant e > O, for the following geometric configurations:

References

18