A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
Abstract
Let be a path graph of vertices embedded in a metric space. We consider the problem of adding a new edge to so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of . Previously, the “continuous” version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our “discrete” version of the problem has not been studied before. We present a linear-time algorithm for the problem.
A preliminary version of this paper appeared in Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020).
Communicated by S.-W. Cheng
Remember to check out the Most Cited Articles! |
---|
Check out these titles in image analysis! |