An improved algorithm for diameter-optimally augmenting paths in a metric space

Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O(nlog3⁡n) time. In this paper, based on new observations and different algorithmic techniques, we present an O(nlog⁡n) time algorithm.