Minimizing the continuous diameter when augmenting a tree with a shortcut
We augment a tree T with a shortcut pq to minimize the largest distance between any two points along the resulting augmented tree T + pq. We study this problem in a continuous and geometric setting where T is a geometric tree in the Euclidean plane, a shortcut is a line segment connecting any two points along the edges of T, and we consider all points on T +pq (i.e., vertices and points along edges) when determining the largest distance along T + pq. The continuous diameter is the largest distance between any two points along edges. We establish that a single shortcut is sufficient to reduce the continuous diameter of a geometric tree T if and only if the intersection of all diametral paths of T is neither a line segment nor a point. We determine an optimal shortcut for a geometric tree with n straight-line edges in O(n log n) time.
|Keywords||Continuous diameter minimization, Network augmentation|
|Series||Lecture Notes in Computer Science|
De Carufel, J.-L. (Jean-Lou), Grimm, C. (Carsten), Schirra, S. (Stefan), & Smid, M. (2017). Minimizing the continuous diameter when augmenting a tree with a shortcut. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-62127-2_26