Finding the best shortcut in a geometric network

M. Farshi, P. Giannopoulos, J. Gudmundsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


Given a Euclidean graph G in Rd 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 + n2 log n) time, resulting in a trivial O(mn3 + n4 log n) time algorithm for computing the optimal shortcut. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n2) space. To reduce the running times we consider several approximation algorithms. Our main result is a (2+e)-approximation algorithm with running time O(nm + n2(log n + 1/e3d)) using O(n2) space.
Original languageEnglish
Title of host publicationAbstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
EditorsM.T. Berg, de
Publication statusPublished - 2005

Fingerprint Dive into the research topics of 'Finding the best shortcut in a geometric network'. Together they form a unique fingerprint.

Cite this