Shortcuts for Geometric Networks — Part I: Paths and Cycles

Carsten Grimm

We seek to augment a network with shortcuts to minimize the largest distance between any two points on the network. We consider this problem in a continuous and geometric setting where:

- the network is a geometric graph embedded into the Euclidean plane,
- shortcuts may connect any two points along the network that may be vertices or points along edges,
- the weight of a shortcut is the Euclidean distance of its endpoints,
- and all points along the edges of the network are taken into account when computing the farthest distance.

In this talk, we characterize optimal shortcuts for paths, convex cycles, and non-convex cycles. Based on these insights, we develop linear-time algorithms for finding an optimal shortcut for a path and for finding a pair of optimal shortcuts for convex cycles. We also briefly summarize some variations of this problem that have been studied and some that have yet to be studied.