Shortcuts for the circle

Abstract: Let

C

be the unit circle in

m a t h b b 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

k g e q 1

emph{shortcuts} on

C

such that the diameter of the resulting graph is minimized. We analyze for each

k

with

1 l e q k l e q 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 + T h e t a (1 / k^{f r a c 23})

for any~

k

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Shortcuts for the circle