Let $C$ be the unit circle in $mathbb{R}^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation problem on $C$, where we want to place $kgeq 1$ emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1leq kleq 7$ what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of~$k$. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is $2 + Theta(1/k^{frac{2}{3}})$ for any~$k$.
Download