Minimizing the continuous diameter when augmenting paths and cycles with shortcuts
We seek to augment a geometric network in the Euclidean plane with shortcuts to minimize its continuous diameter, i.e., the largest network distance between any two points on the augmented network. Unlike in the discrete setting where a shortcut connects two vertices and the diameter is measured between vertices, we take all points along the edges of the network into account when placing a shortcut and when measuring distances in the augmented network. We study this network augmentation problem for paths and cycles. For paths, we determine an optimal shortcut in linear time. For cycles, we show that a single shortcut never decreases the continuous diameter and that two shortcuts always suffice to reduce the continuous diameter. Furthermore, we characterize optimal pairs of shortcuts for convex and non-convex cycles. Finally, we develop a linear time algorithm that produces an optimal pair of shortcuts for convex cycles. Apart from the algorithms, our results extend to rectifiable curves. Our work reveals some of the underlying challenges that must be overcome when addressing the discrete version of this network augmentation problem, where we minimize the discrete diameter of a network with shortcuts that connect only vertices.
|Keywords||Cycles, Diameter, Network augmentation, Paths, Shortcuts|
|Conference||15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016|
De Carufel, J.-L. (Jean-Lou), Grimm, C. (Carsten), Maheshwari, A, & Smid, M. (2016). Minimizing the continuous diameter when augmenting paths and cycles with shortcuts. In Leibniz International Proceedings in Informatics, LIPIcs (pp. 27.1–27.14). doi:10.4230/LIPIcs.SWAT.2016.27