finding the best shortcut in a geometric network
Given a Euclidean graph G in R d with n vertices and m edges we consider the problem of adding a shortcut such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a Euclidean graph runs in O(mn+n 2 log n) time, resulting in a trivial O(mn 3 +n 4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n 4 ) time using O(n 2 ) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+?)-approximation algorithm with running time O(nm+n 2 (log n+1/? 3d )) using O(n 2 ) space.
geometric networks approximation algorithms computational geometry