Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space

The stretch factor and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and the metric space, respectively. In this paper we show that computing the stretch factor of a rectilinear path in L ₁ plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log ² n) time algorithm for computing the stretch factor or maximum detour of a path embedded in the plane with a weighted fixed orientation metric defined by σ < 2 vectors and a worst-case O(n log ^d n) time algorithm to d < 3 dimensions in L ₁-metric. We generalize the algorithms to compute the stretch factor or maximum detour of trees and cycles in O(σn log ^d+1 n) time. We also obtain an optimal O(n) time algorithm for computing the maximum detour of a monotone rectilinear path in L ₁ plane.