## Abstract

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_{1} space has a lower bound of Ω(n logn) in the algebraic computation tree model and describe a deterministic O(n log^{2} n) time algorithm. On the other hand, we give a deterministic O(n log^{2} n) time algorithm for computing the maximum detour of a rectilinear path P in L_{1} space and obtain an O(n) time algorithm when P is a monotone rectilinear path.

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

Title of host publication | Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings |

Pages | 121-131 |

Number of pages | 11 |

Edition | PART 2 |

DOIs | |

Publication status | Published - 2010 |

Externally published | Yes |

Event | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: 15 Dec 2010 → 17 Dec 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | PART 2 |

Volume | 6507 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 |
---|---|

Country/Territory | Korea, Republic of |

City | Jeju Island |

Period | 15/12/10 → 17/12/10 |

## Keywords

- L metric
- Manhattan plane
- dilation
- maximum detour
- rectilinear path
- spanning ratio

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science (all)

## Fingerprint

Dive into the research topics of 'Spanning ratio and maximum detour of rectilinear paths in the L_{1}plane'. Together they form a unique fingerprint.