Minimizing the continuous diameter when augmenting a geometric 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(nlogn) time.
|Augmentation, Continuous diameter, Geometric network, Shortcut, Tree|
|Organisation||School of Computer Science|
De Carufel, J.-L. (Jean-Lou), Grimm, C. (Carsten), Maheshwari, A, Schirra, S. (Stefan), & Smid, M. (2020). Minimizing the continuous diameter when augmenting a geometric tree with a shortcut. Computational Geometry. doi:10.1016/j.comgeo.2020.101631