Spanning Ratio and Maximum Detour of Rectilinear Paths in the L 1 Plane.

The spanning ratio and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and metric space, respectively. In this paper we show that computing the spanning ratio of a rectilinear path P in L₁ space has a lower bound of Ώ(n logn) in the algebraic computation tree model and describe a deterministic O(n log²n) time algorithm. On the other hand, we give a deterministic O(n log²n) time algorithm for computing the maximum detour of a rectilinear path P in L₁ space and obtain an O(n) time algorithm when P is a monotone rectilinear path. [ABSTRACT FROM AUTHOR]