## Abstract

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 _{1} plane has a lower bound of Ω(n log n) in the algebraic computation tree model and describe a worst-case O(σn log ^{2} 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 _{1}-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 _{1} plane.

Original language | English |
---|---|

Pages (from-to) | 45-60 |

Number of pages | 16 |

Journal | International Journal of Computational Geometry and Applications |

Volume | 22 |

Issue number | 1 |

DOIs | |

Publication status | Published - Feb 2012 |

Externally published | Yes |

## Keywords

- L metric
- Rectilinear path
- cycle
- dilation
- maximum detour
- spanning ratio
- stretch factor
- tree
- weighted fixed orientation metric

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics